Ordered Sets & Sorted Structures

Keep data sorted as it mutates — O(log n) insert/delete plus successor/predecessor, rank, and range queries, with the Python options and when to prefer a heap or BIT.

The need

Sometimes you must keep a collection sorted while inserting and deleting, and ask for “the smallest element ≥ x,” the rank of a value, the k-th smallest, or a window min/max. A hash set gives O(1) membership but no order; a heap gives the single extreme but no arbitrary search. A balanced BST / ordered set gives O(log n) insert, delete, and neighbor/rank queries — the missing middle ground.

What it supports (and the underlying structure)

Backed by a self-balancing BST (red-black/AVL) or a skip list:

add / remove — O(log n)
bisect (lower/upper bound) — first element ≥/> x — O(log n)
predecessor / successor — neighbors of a value
rank / select — “how many are < x” / “the k-th smallest” (with an order-statistics tree)
ordered iteration

In Python

There’s no built-in balanced BST, so use:

sortedcontainers.SortedList — O(log n) add/remove, bisect_left/right, index access (k-th smallest). The practical workhorse for interviews that allow it.
bisect on a plain list — O(log n) search but O(n) insert (array shift); fine when inserts are rare or the list is small.

from sortedcontainers import SortedList
sl = SortedList()
sl.add(5); sl.add(1); sl.add(3)
i = sl.bisect_left(4)        # first index with value >= 4  → 2
sl[0]                        # smallest;  sl[-1] largest;  sl[k] k-th smallest
sl.remove(3)

(Java: TreeMap/TreeSet; C++: std::set/std::map and lower_bound.)

Where it wins

Nearest value / successor-predecessor — “Contains Duplicate III” (keep a window as a sorted set, check neighbors within range); “find the closest element.”
Sliding window min/max — a sorted set, or a monotonic deque for O(n) (see the sliding-window/stacks primers).
Sliding window median — a balanced multiset (or two heaps).
Running order statistics / rank — “Count of Smaller Numbers After Self,” “number of range sums” (also doable with a Fenwick tree — see the segment-tree primer).
Interval booking — keep sorted starts/ends and binary-search overlaps (“My Calendar”).

Ordered set vs heap vs BIT

Need	Reach for
Only the single min/max, repeatedly	heap (lighter)
Arbitrary-position ordered queries as data mutates	ordered set
Prefix sums/counts with point updates over an index range	Fenwick / segment tree
Static, no updates	sort + binary search

Pitfalls

bisect on a list for frequent inserts — O(n) per insert; use SortedList.
Duplicates — decide between a sorted set (unique) and a sorted list/multiset (allows repeats); SortedList allows duplicates.
Availability — if sortedcontainers isn’t allowed, you may need a Fenwick tree (for rank/count) or two heaps (for median) instead.

Choosing in an interview

If the problem needs ordered queries on changing data — nearest/rank/k-th/window-extreme — reach for an ordered set; if you only ever need one extreme, a heap is lighter; if it’s rank/count over an integer domain, a Fenwick tree is often the intended O(log n) tool.