Sign in to watch this lesson
Advanced - Trees Ā· 4:48
LCA by Binary Lifting
Binary lifting stores, for every vertex, its ancestors 1, 2, 4, 8, ... levels up, each built as two jumps of the level below, in O(n log n) time and memory. A lowest-common-ancestor query lifts one vertex from the largest jump down while it stays below the other's ancestors, so it costs O(log n), and the same table gives distances, k-th ancestors and path aggregates. For trees that grow leaf by leaf under tight memory, Harel-Tarjan style jump pointers keep one pointer per vertex with O(1) work per new leaf.
You will learn
- Build the binary-lifting table up[j][v] = up[j-1][up[j-1][v]] with the root as its own parent
- Answer LCA queries by lifting one vertex while it stays below the other's ancestors, using tin/tout for the ancestor test
- Use the table for distances, k-th ancestors and path aggregates such as the minimum edge on a path
- Explain when the n log n table is too big and how one jump pointer per vertex supports O(1) leaf insertion