Augmenting Data Structures: Order-Statistics Trees and Interval Trees

A red-black tree gives $O(\log n)$ search, insertion, and deletion — but nothing else out of the box: it cannot answer "what is the rank of this key?" or "which stored interval overlaps this query point?" without an $O(n)$ scan. Augmentation is the general technique for extending a balanced tree with extra per-node fields that answer new query types in $O(\log n)$, without sacrificing the balance guarantee — provided the new fields can be recomputed cheaply after a rotation. This note states the general augmentation recipe and applies it to two named structures: the order-statistics tree (rank/select queries) and the interval tree (overlap queries).