Sign in to watch this lesson
Advanced - Trees Ā· 4:28
LCA via Euler Tour + RMQ
A depth-first search that writes a vertex on entry and again after each child returns produces an Euler tour of 2n - 1 entries. The lowest common ancestor of u and v is the shallowest entry between their first appearances, so LCA becomes a range-minimum query over heights. A sparse table answers it with two overlapping power-of-two blocks in O(1) after O(n log n) preprocessing, which on this Mac answered 10^7 queries in about a third of a second.
You will learn
- Build the Euler tour (2n - 1 entries), the height of each entry and first[v] with one iterative DFS
- Explain why the shallowest entry between first[u] and first[v] is LCA(u, v)
- Answer the range minimum in O(1) with a sparse table of two overlapping power-of-two blocks, comparing heights
- Choose between sparse table, segment tree and binary lifting from the query volume, memory and whether the tree changes