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.
Least you need to know
- Store the
2^j-th ancestor for each node and each relevantj. - 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 nodev - k — number of levels to climb
- set bit — a power of two present in the binary expansion of
k
Worked example
- If
k = 13, write13 = 8 + 4 + 1. - From node
v, jump to the2^3-ancestor, then the2^2-ancestor of that node, then the2^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 it
- 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.
Next recommended lesson
Continue through this topic with Least You Need to Know: Binary Search Invariants and Boundary Updates.
Least You Need to Know: Binary Search Invariants and Boundary UpdatesRelated lessons
Keep going with nearby lessons in the same topic.