GTOIgraph theory, redesigned

Chapter 10 · Lowest Common Ancestor

LCA via Range Minimum Query

Reduce LCA to RMQ on an Euler tour, answer in O(1), and see why the reduction is exact.

  • hard
  • time n log n pre, O(1) query
  • space n log n
  • 1 snippet
  • sparse table
  • reduction
Read first
TheoremThe 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 ≠ v,

lca(u,v) = arg mini ∈ [pos[u], pos[v]] depth(E[i]),   pos[x] = 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 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 ≥ 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). ∎

cppeuler-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 (Sparse Table and RMQ).

Watch outTwo 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

The tour's depth array changes by exactly ± 1 between neighbours — a ±1 RMQ, which is strictly easier than general RMQ:

  1. Cut E into blocks of size b = ⌊ log n / 2 ⌋.
  2. A block's shape is determined by 2b-1 up/down steps — O(n) blocks but only 2b-1 = O(√n) distinct types. Precompute the in-block answer for every type by brute force: O(√n · b2) = 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.

NoteDo not do this in a contest

The O(1)-query advantage is worth ~4–6× over binary lifting only when q ≳ 106 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 (Tarjan's Offline LCA) is O((n+q)α) with less memory than either, and is the actual fastest option in practice for large q.

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 (Entry/Exit Times and the Euler Tour) and makes dynamic trees hard (linking changes the tour).
  • It proves LCA ≤m RMQ, and RMQ ≤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 (Segment Tree).