Section 7.1.3: Bitwise Tricks and Techniques

Exercise 151. [22] [22] Conversely, show that any algorithm for range minimum queries can be used to find nearest common ancestors, with essentially the same efficiency.

Verified: yes
Solve time: 4m12s

---

We correct the reduction by using the proper Euler tour RMQ construction, not the incorrect interval on first-occurrence indices alone.

Correct solution

Let $T$ be a rooted tree on vertices ${1,\dots,n}$ with root $r$. Let $\delta(v)$ denote the depth of $v$.

We assume we are given a data structure that supports range minimum queries (RMQ) on an array in constant query time after preprocessing with comparable efficiency.

We show how to build an RMQ instance such that each nearest common ancestor (NCA) query becomes a single RMQ query.

1. Euler tour with full visitation sequence

Perform a depth-first search of $T$ starting at $r$. Each time a vertex is visited during the DFS traversal, record it, including repeated visits when backtracking. This produces an Euler tour sequence

$$ E = (e_1, e_2, \dots, e_{2n-1}). $$

Define the depth array

$$ D_t = \delta(e_t). $$

2. First occurrence array

For each vertex $v$, define

$$ \mathrm{first}(v) = \min { t : e_t = v }. $$

3. Key RMQ interval

For two vertices $u,v$, define

$$ i = \mathrm{first}(u), \quad j = \mathrm{first}(v), \quad \text{and assume } i \le j. $$

We will show that

$$ \mathrm{nca}(u,v) = e_k \quad \text{where } k \in \arg\min_{t \in [i,j]} D_t. $$

4. Crucial structural fact

Lemma (Euler tour minimum property)

In the Euler tour sequence $E$, between the first occurrence of $u$ and the first occurrence of $v$, the traversal exactly captures all necessary ascents and descents in the tree path between $u$ and $v$. In particular:

1. The Euler tour segment $E[i..j]$ contains every vertex on the unique tree path between $u$ and $v$, including their nearest common ancestor $a = \mathrm{nca}(u,v)$.
2. Every occurrence of a vertex in $E[i..j]$ has depth at least $\delta(a)$, and the vertex $a$ itself appears in this segment.

5. Proof of the lemma

Let $a = \mathrm{nca}(u,v)$.

(i) The LCA appears in the interval

During DFS, the first time we reach $u$, the traversal is inside the subtree of $a$, since $a$ is an ancestor of $u$. Similarly for $v$.

On the unique tree path from $u$ to $v$, the DFS must ascend from $u$ to $a$, and then descend to $v$. This ascent necessarily visits $a$ at some time between the first visits of $u$ and $v$. Hence, there exists $k \in [i,j]$ such that $e_k = a$.

(ii) No vertex in the interval is above $a$

Every vertex encountered in $E[i..j]$ is either:

• in the subtree of $a$, or
• on the path from $a$ down to $u$ or $v$, or
• part of DFS excursions that return to $a$ before moving toward the other subtree.

In all cases, no vertex strictly above $a$ can appear in this segment, because leaving the subtree of $a$ would require passing through $a$, and that would already place the traversal outside the interval structure defined by first occurrences of $u$ and $v$.

Thus, for all $t \in [i,j]$,

$$ \delta(e_t) \ge \delta(a). $$

6. RMQ characterization

From the lemma:

• $a$ appears in $E[i..j]$,
• every value in $D[i..j]$ is at least $\delta(a)$,
• $D_k = \delta(a)$ for some $k \in [i,j]$.

Therefore the minimum value of $D[i..j]$ is exactly $\delta(a)$, and any index achieving the minimum corresponds to a vertex whose depth equals that of $a$. Since depths strictly increase away from the root along any path, the only such vertex in this interval is $a$ itself.

Hence,

$$ \arg\min_{t \in [i,j]} D_t = a = \mathrm{nca}(u,v). $$

7. Correct reduction

We conclude:

$$ \mathrm{nca}(u,v)

e_{\arg\min_{t \in [\mathrm{first}(u),\mathrm{first}(v)]} D_t}. $$

Thus each NCA query reduces to a single RMQ query on the depth array $D$, with vertex recovery via $E$.

8. Complexity

• Euler tour construction: $O(n)$
• depth array and first occurrences: $O(n)$
• each NCA query: one RMQ query plus constant-time lookup
• preprocessing overhead matches that of the RMQ structure

Hence the reduction preserves asymptotic efficiency up to constant factors.

Conclusion

Any RMQ algorithm can be used to compute nearest common ancestors by building the Euler tour depth array and reducing each NCA query to a single RMQ query on an interval of that array.