داده‌ساختار ‎ Disjoint-Set‎ با ‎Path-Compression‎ را در به‌ترین حالت نظر بگیرید. می‌خواهیم این داده ساختار را طوری تغییر دهیم تا علاوه بر اعمال ‎Find(x)‎ و Merge($S_1$‎, ‎$S_2$)‎ بتواند عمل Historical-Find($x,y,t$)‎ را هم انجام دهد. این عمل به این معنی است که آیا اشیاء ‎$x$‎ و ‎$y$‎ در زمان ‎$t$‎ در یک مجموعه بوده‌اند یا خیر. منظور از زمان ‎$t$‎، زمانی است که ‎$t$‎امین عمل برروی این داده‌ساختار انجام می‌شود.

اگر تعداد اعضای درون داده‌ساختار ‎$n$‎ باشد، نشان دهید چگونه می‌توان با حافظه مصرفی ‎${\cal O}(n)$‎ برای کلّ داده‌ساختار و بدون تغییر در زمان اجرای دو عمل دیگر، کاری کرد تا هر عمل ‎ Historical-Find‎ در زمان ‎${\cal O}(\lg n)$‎ پاسخ داده شود. روش خود را دقیق و با تحلیل ارائه کنید.

• سوال بعد
• سوال قبل