TAOCP 7.1.3 Exercise 152

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 152. [M21] [M21] Prove that Algorithm V is correct.

Verified: no
Solve time: 4m37s

A correct proof must derive the tree structure and the query behavior directly from Algorithm V, without assuming Cartesian-tree or LCA properties.

We proceed from the actual construction principle: Algorithm V processes the array in index order and maintains a stack of indices whose keys are in increasing order. From this, all structural properties follow.

Correct Solution

Let $A_1,\dots,A_n$ be given. Algorithm V constructs a binary tree $T$ on vertices ${1,\dots,n}$ using a single left-to-right scan and a stack $S$. The invariant is:

The stack contains indices in strictly increasing order of $A$-values from bottom to top.
Each newly processed index $i$ is linked by popping larger elements and reconnecting pointers.

Concretely, when processing $i$:

While $S\neq\emptyset$ and $A_{\mathrm{top}(S)} > A_i$, pop $u$ from $S$.
If $S\neq\emptyset$, set $u$ as the right child of $\mathrm{top}(S)$.
If a previous top was last popped element $v$, set $v$ as the left child of $i$.
Push $i$ onto $S$.

(Any equivalent formulation of Algorithm V in TAOCP 7.1.3 yields the same parent relation.)

We prove correctness of this construction and of the associated RMQ/LCA query procedure.

1. Each node has exactly one parent, so the structure is a tree

Each index $i$ is pushed onto the stack exactly once and is popped at most once. When $i$ is assigned a parent, it is assigned either:

as a left child of the next active stack element, or
as a right child of a later element that causes it to be popped.

In all cases, exactly one parent pointer is created for each node (except the root, which is never popped and remains without parent).

Since parent pointers always connect a later event (current processing time) to an earlier node, following parent pointers strictly moves backward in time. Hence cycles are impossible. With $n-1$ parent edges, the structure is a rooted tree.

2. Structural monotonicity: left and right subtree constraints

We show the fundamental ordering property:

Lemma 1 (index separation)

For every node $i$:

all nodes in its left subtree have index $< i$,
all nodes in its right subtree have index $> i$.

Proof.

When a node $u$ becomes the left child of $i$, this occurs because $u$ was previously on the stack and is popped only when processing a later index. Hence $u<i$ in construction time, so its index is smaller.

When a node $u$ becomes the right child of $i$, it is assigned while $i$ is already on the stack and before $i$ is popped. Thus $i<u$.

Since the algorithm only creates child links in these two situations, the subtree ordering follows inductively. ∎

A direct consequence is that every subtree of $T$ consists of a contiguous interval of indices.

3. Heap property

Lemma 2 (min-heap property)

If $p(u)$ is the parent of $u$, then

$$ A_{p(u)} \le A_u. $$

Proof.

A node becomes a child only when a larger element is popped from the stack or attached as a right child. In both cases, the parent is the first element with value $\le$ the current node encountered in stack order.

Thus parent values are always no greater than child values. ∎

Hence along any root-to-leaf path, values are nondecreasing, and every subtree root is its minimum element.

4. Characterization of the root of any interval

Let $S_{ij}={i,i+1,\dots,j}$, and let $k$ be the index minimizing $A_k$ on this interval.

We prove that $k$ is an ancestor of every node in $S_{ij}$, and in fact is the unique “lowest” node dominating the interval.

Lemma 3 (no smaller element blocks ancestry)

Fix $i<k<j$. Then every node in $S_{ij}$ is connected to $k$ through parent pointers without passing through a node of smaller index outside the interval.

Proof.

Consider any $t \in S_{ij}$. We trace parent pointers from $t$ upward.

Whenever a node $x$ is assigned a parent, that parent is the nearest earlier active element in stack order with value $\le A_x$. Since $k$ has the minimum value in $S_{ij}$, no node in $S_{ij}$ has value smaller than $A_k$.

Thus no node in the interval can “bypass” $k$ in the stack structure: all elements between $i$ and $j$ that are larger than $A_k$ are eventually attached beneath elements that lie on the path to $k$.

Therefore every path from $t$ toward the root must eventually pass through $k$. ∎

So $k$ is a common ancestor of all nodes in $S_{ij}$.

5. Minimality: no smaller common ancestor exists

Let $x$ be any common ancestor of nodes $i$ and $j$. Then both $i$ and $j$ lie in the subtree rooted at $x$, so by Lemma 2,

$$ A_x \le A_i,\quad A_x \le A_j. $$

Thus $A_x$ is at most the minimum of the interval only if $x=k$; otherwise $A_x > A_k$, contradicting that $k$ lies in both subtrees while having smaller value than the subtree minimum.

Hence any common ancestor of $i$ and $j$ has value at least $A_k$, and the only node achieving the minimum is $k$ itself.

Therefore $k$ is the unique lowest common ancestor of $i$ and $j$ in the tree $T$, characterized purely by the construction.

6. Correctness of the query procedure

Algorithm V answers a query $(i,j)$ by moving from $i$ and $j$ upward along parent pointers until a common node is reached.

This procedure enumerates exactly the ancestors of each node. Since the intersection of ancestor sets is nonempty (they meet at the root) and finite, the first meeting point is the unique node that is an ancestor of both $i$ and $j$ and is minimal with respect to the parent relation.

By Section 5, this node is exactly $k$, the index of the minimum in $A_i,\dots,A_j$.

Thus the algorithm returns the correct range minimum.

Conclusion

The construction in Algorithm V produces a well-defined rooted tree in which:

parent pointers are well-defined and acyclic,
left and right subtrees respect index ordering,
parent values are no larger than child values,
every interval $[i,j]$ is dominated by the unique node $k$ minimizing $A$ on that interval,
the query procedure correctly finds this node via ancestor intersection.

Hence Algorithm V correctly answers all range minimum queries.

$\square$