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.

جو کم از کم جاننا ضروری ہے

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.

اہم علامتیں

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`

مختصر حل شدہ مثال

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.

عام غلطیاں

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.

اس قسم کے سوال کو کیسے پہچانیں

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.