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

הפעולות הנדרשות הן:

• insert(S, x): מכניסה איבר עם מפתח \(x\) למבנה \(S\). זמן ריצה: \(O(\log n)\).
• find(S, x): מוצאת איבר עם מפתח \(x\) במבנה \(S\). אם האיבר אינו קיים, הפעולה מחזירה NIL. זמן ריצה: \(O(\log n)\).
• inversions(S, x): אם קיים במבנה איבר עם מפתח \(x\), הפעולה מחזירה את מספר האיברים \(y\) במבנה הגדולים מ-\(x\) והוכנסו ל-\(S\) לפניו. זמן ריצה: \(O(1)\).