Binary Lifting

Given a tree where each node has a parent, a common question is: "starting from node $v$, where do you land after moving up $k$ ancestors?" Doing this naively — walking up one parent at a time — takes $O(k)$ steps per query, which is slow if you need to answer many such queries with large $k$. Binary lifting precomputes, for every node, where it lands after $1, 2, 4, 8, \dots$ steps (powers of two), then answers any query by combining a handful of these precomputed jumps — the same way any integer $k$ can be written as a sum of powers of two.

$$\text{up}[v][j] = \text{up}\big[\, \text{up}[v][j-1] \,\big][j-1]$$

says: the node reached from $v$ after $2^j$ steps is whatever you reach after $2^{j-1}$ steps from wherever $2^{j-1}$ steps already got you — doubling the jump length each time you already know the previous one. To answer "$k$ steps from $v$," write $k$ in binary and apply the jump table only for the powers of two that are set, in $O(\log k)$ steps rather than $O(k)$.

Worked example

To find the ancestor 13 steps above node $v$: $13 = 8 + 4 + 1$ in binary ($1101_2$). Look up the precomputed 8-step jump from $v$ to get node $u$, then the precomputed 4-step jump from $u$ to get node $w$, then the precomputed 1-step jump from $w$ — three table lookups total, instead of walking up 13 individual parent pointers one at a time.

This same doubling trick, applied with an LCA-finding rule at each level, is the standard way to answer lowest-common-ancestor queries in $O(\log n)$ time after an $O(n \log n)$ preprocessing step, rather than walking both nodes up one level at a time.