فرض کنید $S$‌ مجموعه‌ای از اعداد حقیقی بین صفر و $n$ است: $S\subseteq \{x|0\leq x \leq n \}$ همچنین $I_j$ برای $j=0,…,n-1$ زیرمجموعه‌هایی از $S$ هستند به طوری که $I_j=\{x|j\leq x <j+1\}$ و $S=\bigcup_{j=_0}^{n-1} I_j$. یک داده ساختار برای دخیره‌ی اعداد مجموعه $S$ (و در نتیجه $I_j$ها) پیشنهاد کنید به طوری که بتوان اعمال زیر را با مرتبه‌های خواسته شده انجام داد:

1. $Insert(x)$: $x$ را به $S$ و نیز به $I_j$ مربوطه اضافه کند( در صورتی که قبلا وجود نداشته باشد.)
2. $Delete(x)$:$x$ را از $S$ و نیز از $I_j$ حذف کند.
3. $List(j)$: عناصر موجود در $I_j$ را بنویسید.

داده ساختار شما باید طوری طراحی شود که اعمال ۱ و ۲ حداکثر در $O(log(|S|))$ و بند ۳ در حداکثر $O(|I_j|)$ انجام شود. داده ساختار و نحوه‌ی انجام اعمال فوق را دقیقا توضیح دهید. احتیاج به الگوریتم نیست.

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