You hold n distinct order sizes and must support insert, delete and select(k), the k-th smallest, all in O(log n). Give two structures that achieve it and say which you would use when the key space is bounded by 10^6 and updates run at a million per second.

You hold n distinct order sizes and must support insert, delete and select(k), the k-th smallest, all in O(log n). Give two structures that achieve it and say which you would use when the key space is bounded by 10^6 and updates run at a million per second.

Approach: Augment a balanced tree with subtree sizes, or index a Fenwick tree by key and descend it. Compare constant factors, memory locality and the assumptions each makes about the keys.

An order statistic tree, or a Fenwick tree over the key space descended by binary lifting, both O(log n). The order statistic tree stores a subtree size in every node, updated on the O(1) rotations that a red-black or AVL rebalance performs, and select(k) descends by comparing k against the left subtree size, subtracting it plus one whenever it goes right. The Fenwick tree stores a count per key and select(k) walks the implicit binary structure from the highest power of two downward, moving right whenever the running prefix count stays below k, which costs O(log U) for a key universe of size U. With keys bounded by 10^6 and a million updates a second the Fenwick tree wins on constants: it is one contiguous array of 10^6 counters, about 20 cache-friendly array touches per operation, with no pointer chasing, no allocation and no rebalancing, while the balanced tree pays a cache miss per level. The tree is right only when the key space is unbounded or too sparse to index directly.

Follow-up: How would you make the Fenwick version support keys arriving from an unbounded space without an offline coordinate compression pass?

Key concepts: order statistic tree, subtree size, fenwick tree, binary lifting.