---
title: "LCA via Range Minimum Query"
summary: Reduce LCA to RMQ on an Euler tour, answer in O(1), and see why the reduction is exact.
difficulty: hard
tags: [sparse table, reduction]
time: n log n pre, O(1) query
space: n log n
prereq: [trees/euler-tour, structures/sparse-table, lca/binary-lifting]
see: [structures/sparse-table, lca/tarjan-offline]
---

:::theorem title="The reduction"
List the vertices in the order a DFS *re-visits* them (append $v$ on entry and after each child returns): $E$ has length $2n-1$. For $u \ne v$,
$$\operatorname{lca}(u,v) = \arg\min_{i \in [\operatorname{pos}[u],\ \operatorname{pos}[v]]} \operatorname{depth}(E[i]), \qquad \operatorname{pos}[x] = \text{first index of } x .$$
:::

:::proof
Between the first appearances of $u$ and $v$, the tour walks up from $u$ to their common ancestor and down to $v$; it cannot go above $\operatorname{lca}(u,v)$ (that vertex separates them) and must visit it (the only way to get from one side to the other). Depth is minimal exactly at the LCA among visited vertices, and every vertex on the up-path has depth $\ge$ its depth. Hence the minimum over the interval is the LCA. The depth of the LCA is attained, so the argmin works even with ties broken arbitrarily (no vertex above the LCA is present, and a tie between two occurrences of the LCA is harmless). ∎
:::

```cpp euler-rmq-lca.cpp
vector<int> E, dep, pos(n, -1);
void tour(int v, int p, int d) {
    pos[v] = E.size(); E.push_back(v); dep.push_back(d);
    for (int to : g[v]) if (to != p) { tour(to, v, d + 1); E.push_back(v); dep.push_back(d); }
}
// Sparse table over dep[], storing the index of the minimum:  build O(m log m), query O(1)
int lca(int u, int v) {
    if (pos[u] > pos[v]) swap(u, v);
    int l = pos[u], r = pos[v], k = __lg(r - l + 1);
    return E[rmq(l, r, k)];              // rmq = argmin over [l, l+2^k) vs [r-2^k+1, r]
}
```
Here $m = 2n-1$, so the preprocess is $O(n \log n)$ and memory $O(n \log n)$ — the *same order* as binary lifting but with $O(1)$ instead of $O(\log n)$ queries, because $\min$ is idempotent and the overlapping blocks are allowed (@structures/sparse-table).

:::warning title="Two implementation traps"
- `pos` must be the **first** occurrence. Using the last (or any) breaks the interval, since the tour between two occurrences of $u$ may dip below and above $v$'s ancestor chain.
- The RMQ compares **depths**, not vertex ids: taking $\min E[i]$ is wrong, and the tree must be the one the tour was built on.
:::

## Linear time, if you really want it {#linear}
The tour's depth array changes by exactly $\pm 1$ between neighbours — a *±1 RMQ*, which is strictly easier than general RMQ:
1. Cut $E$ into blocks of size $b = \lfloor \log n / 2 \rfloor$.
2. A block's shape is determined by $2^{b-1}$ up/down steps — $O(n)$ blocks but only $2^{b-1} = O(\sqrt n)$ distinct *types*. Precompute the in-block answer for every type by brute force: $O(\sqrt n \cdot b^2) = O(n)$.
3. Sparse table over block minima: $O((n/b) \log(n/b))$, query $O(1)$.
4. Answer a query as (suffix of block of $l$) ⊕ (whole blocks between) ⊕ (prefix of block of $r$) using the type table.

This is Bender–Farach-Colton: $O(n)$ preprocess, $O(1)$ query, $O(n)$ space — the theoretical optimum.

:::note title="Do not do this in a contest"
The $O(1)$-query advantage is worth ~4–6× over binary lifting only when $q \gtrsim 10^6$ and you are memory-bound rather than compute-bound; the general sparse table variant is already $O(1)$ with 10 lines and no case analysis. If you are offline with *no* updates, Tarjan's algorithm (@lca/tarjan-offline) is $O((n+q)\alpha)$ with less memory than either, and is the actual fastest option in practice for large $q$.
:::

:::props title="Why the reduction matters beyond LCA"
- It is the canonical example of **reducing a tree problem to a sequence problem**: the same move turns subtrees into intervals (@trees/euler-tour) and makes dynamic trees hard (linking changes the tour).
- It proves LCA $\le_m$ RMQ, and RMQ $\le_m$ LCA too (via Cartesian trees): the two problems are *equivalent*, so a linear-time RMQ and a linear-time LCA preprocess stand or fall together.
- Cartesian tree construction is the reduction in the other direction, and it is 8 lines with a stack (@structures/segment-tree).
:::