The LCA Problem Revisited
📜 Abstract
We present a very simple algorithm for the Least Common Ancestor problem. We thus dispel the frequently held notion that an optimal LCA computation is unwieldy and unimplementable. Interestingly, this algorithm is a sequentialization of a previously known PRAM algorithm of Berkman, Breslauer, Galil, Schieber, and Vishkin [1].
✨ Summary
The paper presents a simple linear-preprocessing, constant-query-time algorithm for the static Least Common Ancestor (LCA) problem. Its main idea is to reduce LCA queries to Range Minimum Queries (RMQ) over the level sequence of an Euler tour of the rooted tree. Because adjacent values in this sequence differ by exactly one, the resulting problem is a restricted ±1 RMQ problem.
The authors solve ±1 RMQ using a block decomposition. Queries within a block are answered by precomputed lookup tables over normalized block types; queries spanning multiple blocks are answered using the minima of the boundary fragments together with a sparse-table structure over block minima. This yields linear preprocessing and space with constant-time queries. They then show that general RMQ can be reduced back to LCA by constructing the Cartesian tree of the input array in linear time. Together, these reductions establish a close algorithmic equivalence between LCA and RMQ.
The paper’s influence is visible in subsequent RMQ, LCA, and longest-common-extension (LCE) research. Fischer and Heun’s later work developed theoretical and practical improvements to RMQ structures and explicitly built on the LCA/RMQ framework associated with this paper. (link.springer.com) The reduction and its lookup-table/block-decomposition strategy are also routinely presented in advanced algorithms courses and lecture materials. (www3.dcc.fc.up.pt) The paper received the Imre Simon Test-of-Time Award at LATIN 2012, recognizing it as the most influential eligible LATIN paper. (microsoft.com)