LCA: How to Solve an Impossible Problem (with Data Structures)

Main Ideas

• The lowest common ancestor (LCA) problem: Given two nodes in a tree, find the deepest node that is an ancestor of both.
• A straightforward method follows each node’s path toward the root and compares the paths. It takes O(n) time in the worst case.
• The challenge is to preprocess the tree in O(n) time so that each later LCA query takes O(1) time. Storing the answer for every pair is too expensive: it requires O(n²) space, and computing those answers directly could take O(n³) time.

Key Reduction: LCA to Range Minimum Queries

A range minimum query (RMQ) asks for the minimum value in a section of an array. The video uses RMQ as a simpler problem to solve, then transforms LCA queries into RMQ queries.

1. From RMQ to LCA: An array can be represented as a recursively constructed tree: choose the array’s minimum as the root, then recursively build subtrees from the portions on either side. The minimum in a range corresponds to the LCA of the range’s endpoints in this tree.
2. From LCA to RMQ: Perform an Euler walk of the tree, recording each visited node and its depth. Nodes appear more than once as the walk returns through the tree.
3. Answer a query: Record each node’s position in the Euler-walk array. For two queried nodes, take the range between their recorded positions. The minimum-depth node in that range is their LCA.
4. The Euler-walk array has O(n) entries: each tree node is recorded on first arrival, and each edge contributes one additional entry as the walk returns.

This reduction means an efficient RMQ data structure can provide an efficient LCA data structure.

RMQ Preprocessing Methods

Sparse Tables

• A simple RMQ table could store the minimum for every possible range, but that requires O(n²) preprocessing and space.
• Instead, precompute minima for ranges whose lengths are powers of two: 1, 2, 4, 8, and so on.
• Build each larger range’s minimum from two previously computed smaller ranges.
• Any query range can be covered by two power-of-two ranges. They may overlap, which is harmless for minimum queries: the answer is the smaller of the two stored minima.
• This gives O(1) query time and O(n log n) preprocessing time and space.

Sparse tables are also useful for other suitable range operations, such as greatest common divisor, bitwise AND, and—in appropriate settings—addition.

Indirection for Linear Preprocessing

To reduce the extra logarithmic factor, the video combines a sparse table over blocks with lookup tables inside blocks.

1. Divide the array into blocks of size proportional to log n.
2. Build a parent array containing the minimum of each block. A query spanning multiple blocks can be answered using:
   • The relevant suffix of the first block
   • The relevant prefix of the last block
   • A parent-array query for the complete blocks in between
3. Use a sparse table on the parent array. Because it is smaller than the original array by roughly the block size, its sparse-table preprocessing takes O(n) time when the block size is proportional to log n.
4. Reuse lookup tables for block patterns. In the Euler-walk depth array, adjacent values differ by exactly +1 or −1. Thus, a block’s pattern is determined by its sequence of rises and falls, rather than its absolute values. Blocks with the same pattern can share a table of answers for all their internal range-minimum queries.
5. Choose blocks slightly smaller than log n. Taking a block size around ½ log n keeps the number of possible block patterns small enough that constructing their lookup tables takes sublinear time, while the parent-array sparse table remains linear-time to build.

Final Method and Complexity

The complete preprocessing pipeline is:

• Convert the tree into an Euler-walk depth array.
• Divide that array into blocks of size about ½ log n and compute each block’s minimum.
• Build a sparse table over the block minima.
• Precompute RMQ lookup tables for the possible ±1 block patterns and associate each actual block with its pattern’s table.
• For each LCA query, translate the nodes to positions in the Euler array and combine the necessary within-block and between-block minima.

The video presents this as achieving O(n) preprocessing and space, with O(1) query time.

Broader Lesson

The solution illustrates how a difficult problem can become manageable by changing perspective: reduce it to a simpler related problem, use a well-understood data structure, and combine that structure with a second technique. The presenter notes that the full construction is more elaborate than many practical LCA solutions require, but emphasizes that reductions, sparse tables, and indirection are reusable algorithmic ideas.

Speakers and Sources

• Speaker: A single narrator/voiceover; no other speakers are identified in the subtitles.
• Other sources: No external sources or additional speakers are named in the subtitles.