Graph Theory37 sections · 1633 units
Open in Course

Applications Beyond Ancestors

(Where binary lifting is used)

Binary lifting is not for ancestor queries. You can use it for:

1.1. LCA in O(logn)O(\log n) per query (as you saw).

2.2. Path queries: find the sum/max/min on a path between two nodes.

3.3. Level ancestor: find the ancestor at a specific depth.

4.4. Jump pointers in graphs: precompute jumps of size 2j2^j in any DAG.

The core idea (precompute power-of-22 jumps, then binary decompose) applies to many problems.