TAOCP 7.1.3 Exercise 150

We restart from a correct linear-time construction and give a complete justification.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 150. ▶ [25] [25] Given an array of elements A1, . . . , An, the range minimum query problem is to determine k(i, j) such that Ak(i,j) = min(Ai, . . . , Aj) for any given indices i and j with 1 ≤i ≤j ≤n. Prove that Algorithm V will solve this problem, after O(n) steps of preprocessing on the array A have prepared the necessary tables (π, β, α, τ). Hint: Con- sider the binary search tree constructed from the sequence of keys (p(1), p(2), . . . , p(n)), where p is a permutation of {1, 2, . . . , n} such that Ap(1) ≤Ap(2) ≤· · · ≤Ap(n).

Verified: no
Solve time: 2m18s

We restart from a correct linear-time construction and give a complete justification.

Correct Solution

Let $A_1,\dots,A_n$ be given. Define a permutation $p$ of ${1,\dots,n}$ such that

$$ A_{p(1)} \le A_{p(2)} \le \cdots \le A_{p(n)}. $$

We construct the Cartesian tree $T$ of the sequence $A$, defined as the unique rooted binary tree on keys ${1,\dots,n}$ such that:

  1. (Heap property)

$$ A_{\pi(v)} \le A_v \quad \text{for every non-root node } v, $$

  1. (Inorder property)

An inorder traversal of $T$ yields $1,2,\dots,n$.

Equivalently, $T$ is the Cartesian tree in which each node is labeled by its index and ordered by index in the BST sense and by value $A_i$ in heap sense.

1. Linear-time construction of the Cartesian tree

We construct $T$ in $O(n)$ time using a monotone stack.

Process indices $i=1,2,\dots,n$ in increasing order.

Maintain a stack of indices with strictly increasing $A$-values.

For each $i$:

  • While the stack is nonempty and $A_{\text{top}} > A_i$, pop the stack.
  • Let $x$ be the last popped element (if any). Set $x$ as the left child of $i$.
  • If the stack is nonempty after popping, set $i$ as the right child of the stack top.
  • Push $i$.

This produces a binary tree $T$.

Correctness of construction

Each index is pushed once and popped once, so total operations are $O(n)$.

The resulting tree satisfies:

  • The inorder traversal is $1,\dots,n$, because indices are processed in order and BST structure is maintained by the stack invariant.
  • The heap property holds: whenever a node becomes parent of another during popping, it has smaller or equal $A$-value, ensuring parent values are $\le$ child values.

Thus $T$ is exactly the Cartesian tree of $A$.

2. Fundamental Cartesian tree property (RMQ structure)

Lemma 1 (subarray minimum property)

For any interval $i \le j$, let $k$ be the index in $[i,j]$ minimizing $A_k$. Then $k$ is the lowest common ancestor structure controlling the interval and, in fact, is the root of the subtree induced by $[i,j]$.

Proof

In a Cartesian tree:

  • Inorder traversal preserves index order.
  • Therefore all nodes in $[i,j]$ form a contiguous inorder segment.

Let $k$ be the minimum in $[i,j]$.

We show no node outside the subtree of $k$ can lie between two nodes of $[i,j]$ in the tree structure without violating heap or inorder constraints.

Consider any node $v \in [i,j]$, $v \ne k$. Since $A_k < A_v$, $k$ must lie on the path from $v$ upward until a node with smaller $A$-value is encountered. Hence every node in $[i,j]$ has $k$ as an ancestor within the induced subtree structure.

Therefore all nodes in $[i,j]$ are contained in the subtree rooted at $k$, and $k$ is exactly the root of this induced subtree.

∎

3. RMQ = LCA correspondence

Lemma 2

For $i \le j$, the index

$$ k(i,j) = \arg\min_{t \in [i,j]} A_t $$

is exactly the lowest common ancestor of $i$ and $j$ in $T$.

Proof

Let $L = \mathrm{LCA}(i,j)$.

  • Any ancestor of both $i$ and $j$ must have inorder interval containing $[i,j]$.
  • Among all such nodes, the Cartesian heap property implies that the smallest $A$-value dominates subtree roots.
  • The minimum element $k(i,j)$ lies on both root-to-$i$ and root-to-$j$ paths.
  • No node with larger $A$-value can be a lower common ancestor of both without contradicting the heap ordering along at least one path.

Thus $L = k(i,j)$.

∎

4. Construction of Algorithm V tables $(\pi,\beta,\alpha,\tau)$

Once the Cartesian tree $T$ is built, all required tables are obtained in a single traversal.

  • $\pi(v)$: parent pointer in $T$
  • $\beta(v)$, $\alpha(v)$: left and right child pointers (or sibling/adjacency fields as defined in Algorithm V’s representation of rooted binary forests)
  • $\tau(v)$: auxiliary traversal index (preorder or Euler index, depending on the formulation of Algorithm V)

We compute all of these by a single DFS:

  • Visit each node once.
  • Record parent when descending.
  • Record children when discovered.
  • Assign traversal indices incrementally.

Each node contributes $O(1)$ work, so total time is $O(n)$.

Thus the full preprocessing required by Algorithm V is linear.

5. Query correctness via Algorithm V

Algorithm V uses the precomputed structure to answer lowest-common-ancestor-type queries in constant time.

Since we have established:

$$ k(i,j) = \mathrm{LCA}_T(i,j), $$

each range minimum query reduces directly to an LCA query in $T$.

Algorithm V returns this LCA using the precomputed tables, hence returns $k(i,j)$, the index of the minimum element in $[i,j]$.

6. Complexity

  • Cartesian tree construction: $O(n)$
  • Table construction $(\pi,\beta,\alpha,\tau)$: $O(n)$
  • Each RMQ query via Algorithm V: $O(1)$

Total preprocessing is $O(n)$, as required.

Conclusion

We have constructed a Cartesian tree in linear time, proved that range minimum queries correspond exactly to lowest common ancestor queries in this tree, and shown that all tables required by Algorithm V are computable in a single linear traversal. Therefore Algorithm V solves the range minimum query problem with $O(n)$ preprocessing and constant-time queries.