הציעו מבנה נתונים S אשר מתחזק n מספרים שלמים ייחודיים ותומך בשגרות הבאות בזמני הריצה המצוינים ליד כל שגרה:

• Insert(S, k): הכנסת המספר השלם k למבנה S, זמן ריצה: \(O(\log n)\).
• Delete(S, x): מחיקת האיבר אליו מצביע x מהמבנה S, זמן ריצה: \(O(\log n)\).
• Change(S, x): שינוי הסימן של המפתח של האיבר x ששייך ל-S, זמן ריצה: \(O(\log n)\).
• Search_Nonnegative(S, k): מחזיר את המפתח האי-שלילי המינימלי ב-S שגדול או שווה למספר השלם k. k אינו בהכרח ערך של מפתח ב-S. זמן ריצה: \(O(\log n)\).
• Med_Negative(S): מחזיר את החציון התחתון מבין ערכי המפתחות השליליים ב-S, זמן ריצה: \(O(\log n)\).

הערה:
בשגרת Change(S, x) הכוונה היא להפוך את הסימן של המפתח של האיבר x משלילי לחיובי או מחיובי לשלילי, למשל אם key(x) = -3 אז לאחר קריאה ל-Change(S,x) יתקיים key(x) = 3.

תארו את האלגוריתמים באופן מילולי ובקצרה, ונתחו בקצרה נכונות וסיבוכיות.