תכננו מבנה נתונים S המאפשר לבצע את הפעולות הבאות בסיבוכיות זמן ריצה של \(O(\log n)\), כאשר \(n\) הוא מספר האיברים במבנה.
הניחו כי כל האיברים במבנה שונים זה מזה.

• insert(S, k): מכניס איבר בעל מפתח \(k\) ל-S.
• find(S, k): מחזיר את האיבר בעל המפתח \(k\) מ-S אם הוא קיים, אחרת מחזיר NIL.
• inversions(S, k): אם קיים במבנה איבר בעל המפתח \(k\), הפעולה מחזירה את מספר ההיפוכים עבור \(k\).

הגדרת היפוך: היפוך עבור איבר \(k\) הוא כל איבר בעל מפתח \(l\) שהוכנס למבנה לפני \(k\) ומקיים \(l > k\).