Algorithms / Binary Lifting
Least You Need to Know: Binary Lifting, Power-of-Two Jumps, and Ancestor Queries
Binary lifting preprocesses jump pointers so ancestor movement can be decomposed into **powers of two**. The main trick is the same as binary representation: any jump length can be written as a sum of power-of-two jumps.
The least you need to know
- Store the `2^j`-th ancestor for each node and each relevant `j`.
- A k-step climb can be decomposed using the set bits of `k`.
- Preprocessing usually costs `O(n log n)`.
- Each query uses at most `O(log n)` jumps.
- Binary lifting also supports fast LCAs after equalizing depths.
Key notation
up[v][j]
the `2^j`-th ancestor of node `v`
k
number of levels to climb
set bit
a power of two present in the binary expansion of `k`
Tiny worked example
- If `k = 13`, write `13 = 8 + 4 + 1`.
- From node `v`, jump to the `2^3`-ancestor, then the `2^2`-ancestor of that node, then the `2^0`-ancestor.
- Only three table lookups are needed instead of climbing one edge at a time.
- The same idea helps equalize depths before finishing an LCA query.
Common mistakes
- Students sometimes think every distance needs its own table column; powers of two are enough.
- Missing null-ancestor handling at the root breaks table building.
- Binary lifting speeds queries only after preprocessing.
How to recognize this kind of problem
- You need many ancestor or LCA queries on a static tree.
- The phrase `k`-th ancestor appears directly.
- Fast repeated climbs are more important than single-query simplicity.