Chapter 10
Lowest Common Ancestor
LCA is the hinge between trees and queries. Four solutions, four different ideas — DSU, sparse tables, DFS order, and decomposition — which is why it is the best practice topic in the book.
6 pages4,578 words8 problems1 interactive
1The LCA ProblemWhat the lowest common ancestor is, the seven distances it answers, and how to choose among four algorithms.2LCA by Binary LiftingThe 12-line precomputation, the two-phase query, and the family of problems it solves beyond LCA.3LCA via Range Minimum QueryReduce LCA to RMQ on an Euler tour, answer in O(1), and see why the reduction is exact.4Tarjan's Offline LCAAnswer all LCA queries in near-linear time with a DFS and a disjoint-set union — no log factor, no table.5LCA by Heavy-Light DecompositionClimbing chains instead of bits — same asymptotics, half the memory, and the same code you need for path queries.6Virtual TreesBuild the minimal subtree spanning k marked vertices in O(k log k) with a stack and LCA — the trick behind a hundred "query on a subset of vertices" problems.