Augmented Binary Trees for Dynamic Sequences and Data Structures

For an augmentation to be useful and efficient, it must satisfy two strict requirements:

1. Subtree Dependency: The value must depend only on the nodes within that specific subtree. It cannot depend on the node's parent or any ancestors.
2. Constant-Time Computation: The value must be computable in $O(1)$ time using only the node's own item and the augmented values already stored in its immediate children.

A classic example is subtree size. For any node $x$, we store the total number of nodes in the subtree rooted at $x$. We calculate this as: $\text{sizeof}(x) = 1 + \text{sizeof}(x.\text{left}) + \text{sizeof}(x.\text{right})$ where $\text{sizeof}(\text{None}) = 0$.

Exam Tip: If you are asked if "node depth" is a valid augmentation, the answer is no. Depth depends on the distance to the root (ancestors), violating the requirement that an augmentation must only depend on the subtree.

Sequence Operations: OS-Select and OS-Rank

With subtree sizes stored at every node, we can perform "Order Statistic" (OS) operations to navigate the sequence by index.

OS-Select (Finding an element by index)

To find the $k$-th element in a sequence, we use OS-Select(x, k). We look at the size of the left subtree to determine the "rank" of the current node $x$ within its subtree. The rank of $x$ is $\text{sizeof}(x.\text{left}) + 1$.

• If $k = \text{rank}$, we have found our node.
• If $k < \text{rank}$, the target is in the left subtree.
• If $k > \text{rank}$, the target is in the right subtree, and we search for the $(k - \text{rank})$-th element there.

OS-Rank (Finding the index of a node)

If we have a pointer to a node $x$ and want to know its position in the sequence, we use OS-Rank. We start with the rank as $\text{sizeof}(x.\text{left}) + 1$ and walk up the tree toward the root. If we are moving up from a right child, we add the size of the parent's left subtree plus one (for the parent itself) to our rank. If we are moving up from a left child, the parent and its right subtree do not precede $x$, so we add nothing.

Maintaining Augmentations

Whenever we modify the tree—such as through insert_at(i, x) or delete_at(i)—the stored augmentation values (like subtree sizes) may become incorrect. To fix this, we perform a repair process.

Because an augmentation at node $x$ only depends on its children, a change at $x$ only affects the values of its ancestors. We perform a single upward pass from the modified node to the root, recomputing the augmentation for each ancestor using the $O(1)$ update rule. Since the height of the tree is $h$, this repair takes $O(h)$ time, ensuring our dynamic operations remain efficient.

Advanced Applications: Range Queries

Augmentations can be used for much more than just sizes. For example, if we store the sum of values in each subtree, we can perform Range-Sum Queries.

By using a "sum augmentation" ($x.\text{sum} = x.\text{item.value} + \text{sum}(x.\text{left}) + \text{sum}(x.\text{right})$), we can find the sum of all elements in a range $[a, b]$in$O(h)$ time. We do this by calculating a "prefix sum" (sum of all elements $\le b$) and a "suffix sum" (sum of all elements $\ge a$) and combining them.

Other powerful applications include:

• Range Max/Min: Storing the maximum or minimum value in a subtree to find the extreme values in a specific range.
• Interval Trees: Augmenting a BST with the maximum high-endpoint of all intervals in a subtree to allow for efficient overlapping interval searches in $O(h)$ time.