Doubling and binary lifting on sequences

In a linked structure, reaching a node far away by following one step at a time costs as many steps as the distance. Jumping 1,000 steps forward one at a time takes 1,000 steps. Binary lifting precomputes where you land after jumping 1, 2, 4, 8, 16, and so on steps, so any jump, however far, is reached by combining a handful of precomputed jumps in $O(\log n)$ time.

The table lift[node][k] stores which node you reach after jumping $2^k$ steps from node. Any jump of d steps decomposes into its binary representation: jumping 13 steps means jumping 8, then 4, then 1, since 13 = 8 + 4 + 1. Each of those three jumps is already precomputed, so the whole distance is covered in three lookups instead of thirteen steps.

Building the table

For each node, the table stores $O(\log n)$ entries: where that node lands after 1, 2, 4, 8, ... steps. The base case is lift[node][0], the node reached after exactly one step, whether that is the next node in a sequence or the parent in a tree.

Every later entry follows from a recurrence: lift[node][k] = lift[lift[node][k - 1]][k - 1]. Jumping $2^k$ steps from node is the same as jumping $2^{k-1}$ steps to reach an intermediate node, then jumping $2^{k-1}$ steps again from there, since $2^{k-1} + 2^{k-1} = 2^k$. Filling the table column by column, smaller powers first, takes $O(n \log n)$ time in total, since each of the $O(\log n)$ columns takes $O(n)$ to fill.

Querying with the table

To jump d steps from a starting node, look at the binary representation of d bit by bit. Whenever a bit is set, make the corresponding precomputed jump and move to the resulting node. Once every bit has been checked, you have reached the destination.

To jump 13 steps, check bit 0 (13 & 1 = 1, so jump $2^0 = 1$), bit 1 (13 & 2 = 2, so jump $2^1 = 2$), and bit 2 (13 & 4 = 4, so jump $2^2 = 4$). Each jump is a single table lookup, so the whole query costs $O(\log d)$.

A linked sequence

Take a linked list where node i points to node i + 1, and you want to find the node 17 steps ahead of node 0.

1import sys2
3
4def main() -> None:5    data = sys.stdin.read().split()6    if not data:7        return8
9    n = int(data[0])10    start = int(data[1])11    target_jump = int(data[2])12
13    # Build a simple linked list: node i -> node i+114    # lift[node][k] = node reached after 2^k steps15
16    # Determine table size needed17    LOG = 2018    lift = [[-1] * LOG for _ in range(n)]19
20    # Base case: lift[i][0] = i+1 (one step ahead)21    for i in range(n - 1):22        lift[i][0] = i + 123
24    # Fill the table: lift[i][k] = where you reach from lift[i][k-1] after 2^(k-1) steps25    for k in range(1, LOG):26        for i in range(n):27            if lift[i][k - 1] != -1:28                lift[i][k] = lift[lift[i][k - 1]][k - 1]29
30    # Query: jump target_jump steps from start31    current = start32    remaining = target_jump33
34    for k in range(LOG - 1, -1, -1):35        if remaining >= (1 << k):36            if lift[current][k] == -1:37                break38            current = lift[current][k]39            remaining -= (1 << k)40
41    if remaining == 0:42        print(f"After jumping {target_jump} steps from {start}, reach node {current}")43    else:44        print(f"Cannot jump {target_jump} steps from {start} (only {target_jump - remaining} steps possible)")45
46
47if __name__ == "__main__":48    main()

20 0 17

After jumping 17 steps from 0, reach node 17

Since the list is a straight chain, jumping 17 steps from node 0 always lands on node 17, which the program confirms after building the table and decomposing 17 into powers of two. The value of the table shows up on a less predictable structure, such as a tree, where "17 steps from here" is not simply "add 17".

To see the table in action, build it for a chain of nodes 0 through 19. lift[i][0] is i + 1 for every node. lift[i][1] composes two single steps: lift[0][1] = lift[lift[0][0]][0] = lift[1][0] = 2. Later columns compose in the same way. To jump 13 steps from node 0, decompose 13 as 8 + 4 + 1. lift[0][3] = 8 reaches node 8, lift[8][2] = 12 reaches node 12 from there, and lift[12][0] = 13 reaches node 13 last. Three table lookups replace thirteen single steps.

Handling nodes with no successor

Some sequences end, or a node may have no valid next step. Store a sentinel value, such as -1, at any table entry that would otherwise point past the end, and check for it before making a jump. If a jump would land on that sentinel, the destination is unreachable, and the query should stop there instead of continuing with an invalid index.

Why the composition is correct, and its cost

Every non-negative integer has a unique binary representation, so any distance can be written as a sum of distinct powers of two. Precomputing jumps of size 1, 2, 4, 8, and so on lets you compose any of those sums. The recurrence works because a jump of $2^{k-1}$ steps behaves the same way no matter which node it starts from: reaching the $2^k$-step destination is exactly reaching the $2^{k-1}$-step destination, then jumping another $2^{k-1}$ steps from there.

Building the table costs $O(n \log n)$: one entry per node per power of two, with $O(\log n)$ powers of two needed to cover a sequence of length $n$. Storing the table costs the same, $O(n \log n)$ space. Once it exists, a single query costs $O(\log d)$, far below the $O(d)$ a naive step-by-step walk would need, which matters when the same structure answers many queries.

Ancestors in a tree

The same table works on tree parent pointers instead of a linear chain. Let lift[node][p] be the node's $2^p$-th ancestor, with the base case lift[node][0] = parent[node] and the same recurrence, lift[node][p] = lift[lift[node][p - 1]][p - 1].

To find the 50th ancestor of a node, decompose 50 as 32 + 16 + 2. lift[node][5] jumps 32 levels up, lift[result][4] jumps 16 more, and lift[result][1] jumps the last 2. The whole query costs $O(\log k)$, fast even when $k$ is as large as $10^6$.

Common mistakes

Confusing the table index with the jump size is the most common error. Column k holds jumps of size $2^k$, not $k$ itself, and lift[node][0] must be the immediate next node, not the node itself. Check the base case carefully before trusting anything built from it.

Forgetting a boundary condition is another. Jumping past the end of a sequence, or above the root of a tree, needs a sentinel value such as -1 to catch it. Without one, a query either reads past the end of the table or loops on invalid data.

A third mistake is writing the wrong recurrence. lift[i][k] = lift[i][k - 1] + 1 looks plausible but only adds one step regardless of k; the correct form, lift[i][k] = lift[lift[i][k - 1]][k - 1], composes two jumps of the previous size. Mixing these up produces a table that runs without error but answers every query wrong.

Recap

Binary lifting precomputes jumps of $2^k$ steps so that any jump of $d$ steps is answered in $O(\log d)$ time, by decomposing $d$ into powers of two. Building the table costs $O(n \log n)$ time and space, after which each query is fast. The same table structure answers "jump forward in a sequence" and "find an ancestor in a tree", since both are really the same recurrence applied to a different notion of "next node".