سوال ۶

داده‌ساختار 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)$ پاسخ داده شود. روش خود را دقیق و با تحلیل ارائه کنید.