Farach-Colton-Bender RMQ/LCA

Purpose: Answer Lowest Common Ancestor queries in $O(1)$ after $O(n)$ preprocessing — no $\log$ anywhere. Also known as the ±1 RMQ or four Russians method.

The Reduction Chain

$\text{LCA}\to \pm 1\text{ RMQ}\to \text{block decomposition}\to O(1)$

1. LCA → RMQ. Take an Euler tour of the tree, recording the depth at each of the $2n-1$ visits. $\mathrm{LCA}(u,v)$ is the shallowest node in the tour segment between the first occurrences of $u$ and $v$ — a range minimum query.
2. The array is ±1. Consecutive Euler-tour depths differ by exactly $\pm 1$, because each step of the tour moves to a parent or a child. This restriction is what buys the constant time.

The Block Trick

Let $m=2n-1$ and block size $b=\frac{1}{2}{\log }_{2}m$.

• Between blocks. Compute the minimum of each block ($m/b$ values) and build a sparse table over those. Cost: $O\left(\frac{m}{b}\log \frac{m}{b}\right)=O(m)$. Any query spanning whole blocks is answered in $O(1)$.
• Inside blocks. A block of length $b$ in a ±1 array is fully determined by its $b-1$ signs, so there are only $2^{b-1}=O(\sqrt{m})$ distinct block types. Precompute, for every type, the answer to every one of the $O(b^2)$ internal query ranges. Total $O(\sqrt{m}\cdot {\log }^{2}m)=o(m)$.
• A query splits into a suffix of one block, some whole blocks, and a prefix of another — three $O(1)$ lookups.

Complexity

• Preprocessing: $O(n)$ time and space
• Query: $O(1)$
• Constant factor: large. Expect 5-10× the constant of a sparse table.

Comparison of LCA methods

Method	Preprocess	Query	Notes
Naive climbing	$O(n)$	$O(n)$	fine for tiny trees
Binary lifting	$O(n\log n)$	$O(\log n)$	the contest default — short, flexible, supports path queries
Euler tour + sparse table	$O(n\log n)$	$O(1)$	~15 lines, excellent constant
Tarjan offline	$O((n+q)\alpha )$	amortized	needs all queries up front
Farach-Colton-Bender	$O(n)$	$O(1)$	asymptotically optimal, big constant
Schieber-Vishkin	$O(n)$	$O(1)$	also optimal, bit-trick based

What to actually write

Euler tour + sparse table. It is $O(n\log n)$ preprocessing, but $n\log n$ with a tiny constant beats $O(n)$ with a huge one for every $n$ you will meet in a contest. Reach for binary lifting if you also need $k$-th ancestor or path aggregates.

Why “four Russians”

The technique of precomputing answers for all possible small blocks is named after Arlazarov, Dinic, Kronrod and Faradzhev, who used it to speed up boolean matrix multiplication. It appears throughout: bitset DP, the $O(n^3/\log n)$ transitive closure, and precomputed popcount tables are all the same idea.

Variants / Use Cases

• Generic RMQ (not ±1) — reduce to LCA via a Cartesian tree, then apply this; still $O(n)/O(1)$
• Lowest Common Ancestor — the topic page
• Range queries on trees — subtree sums, path queries via Euler tour + BIT
• Schieber-Vishkin — the other $O(n)/O(1)$ LCA, with a smaller constant in practice