184. How does an order-statistic tree support rank and select queries?
HardTrees
Technical
Show model answer
Store in each node the size of its subtree. `select(k)` (the kth smallest) compares k with the left size L: equal to L + 1 returns the node, smaller goes left, larger goes right with k - L - 1. `rank(x)` walks down and, each time it moves right, adds L + 1 for the skipped node and its left subtree.
On a balanced tree (AVL or red-black) both queries are O(log n). Insertions and deletions must update sizes along the path, and every rotation must recompute the sizes of the two rotated nodes, so updates stay O(log n).