Skip to content

Binary Lifting Successor

You're standing on node \(x\) in a functional graph. Someone asks: "Where will you be after \(10^9\) steps?" Following edges one by one would take a billion operations. Binary lifting answers in 30.

The Problem

Binary lifting table: up[k][v] stores the 2^k-th successor of v

Given a functional graph \(f: \{1,\ldots,N\} \to \{1,\ldots,N\}\) and queries \((x, k)\), find \(f^{(k)}(x)\) -- the node reached by applying \(f\) exactly \(k\) times starting from \(x\).

Naive approach: follow \(f\) one step at a time. Time per query: \(O(k)\). When \(k = 10^9\), that's way too slow.

The Binary Lifting Idea

Precompute power-of-two jumps:

  • \(\text{up}[x][0] = f(x)\) -- the \(2^0 = 1\)-step successor.
  • \(\text{up}[x][1] = f(f(x))\) -- the \(2^1 = 2\)-step successor.
  • $\text{up}[x][j] = $ the \(2^j\)-step successor of \(x\).

The recurrence is simple: \(\text{up}[x][j] = \text{up}[\text{up}[x][j-1]][j-1]\).

To jump \(2^j\) steps, first jump \(2^{j-1}\) steps, then jump \(2^{j-1}\) more.

const int LOG = 30;
vector<vector<int>> up(n + 1, vector<int>(LOG));
for (int i = 1; i <= n; i++) up[i][0] = f[i];
for (int j = 1; j < LOG; j++)
    for (int i = 1; i <= n; i++)
        up[i][j] = up[up[i][j-1]][j-1];

Precomputation: \(O(N \log K)\) time and space, where \(K\) is the maximum query value.

Answering a Query

Binary lifting jump: decompose k into powers of 2 for O(log k) queries

Decompose \(k\) into binary. For each set bit \(j\), jump \(2^j\) steps.

int query(int x, int k) {
    for (int j = 0; j < LOG; j++) {
        if (k & (1 << j)) {
            x = up[x][j];
        }
    }
    return x;
}

Time per query: \(O(\log K)\).

Trace

Function: \(f = [-, 3, 1, 4, 2, 6, 5]\) (\(N = 6\)). Query: start at node 1, take \(k = 5\) steps.

First, the precomputation table:

Node up[·][0] up[·][1] up[·][2]
1 3 4 1
2 1 3 4
3 4 2 3
4 2 3 4
5 6 5 6
6 5 6 5

Query \((x=1, k=5)\). Binary of 5 = 101.

Bit \(j\) Bit set? Action Current node
0 Yes \(x = \text{up}[1][0] = 3\) 3
1 No Skip 3
2 Yes \(x = \text{up}[3][2] = 4\) 4

Verify by following \(f\) manually: \(1 \to 3 \to 4 \to 2 \to 1 \to 3\). After 5 steps: node 3. Wait, that doesn't match.

Let me recheck. \(f(1) = 3\), \(f(3) = 4\), \(f(4) = 2\), \(f(2) = 1\), \(f(1) = 3\). So after 5 steps from 1: node 3.

The table: $\text{up}[3][2] = $ 4 steps from 3 = \(3 \to 4 \to 2 \to 1 \to 3\). That's node 3, not 4. Let me recompute.

\(\text{up}[3][0] = 4\). \(\text{up}[3][1] = \text{up}[\text{up}[3][0]][0] = \text{up}[4][0] = 2\). \(\text{up}[3][2] = \text{up}[\text{up}[3][1]][1] = \text{up}[2][1] = 3\).

Corrected table:

Node up[·][0] up[·][1] up[·][2]
1 3 4 1
2 1 3 2
3 4 2 3
4 2 1 4

Query \((x=1, k=5)\). \(k = 101_2\).

Bit \(j\) Bit set? Action Current node
0 Yes \(x = \text{up}[1][0] = 3\) 3
2 Yes \(x = \text{up}[3][2] = 3\) 3

Answer: 3. Matches the manual trace.

Key insight. Binary lifting is the same idea as fast exponentiation. Instead of multiplying a number, you're composing a function. Any \(k\) can be decomposed into at most \(\log k\) powers of 2, so \(\log k\) lookups suffice.

CSES Planets Queries I

Problem. \(N\) planets, each with a teleporter to one other planet. \(Q\) queries: starting at planet \(x\), where are you after \(k\) teleportations?

This is the exact problem binary lifting solves.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    const int LOG = 30;
    vector<vector<int>> up(n + 1, vector<int>(LOG));
    for (int i = 1; i <= n; i++) scanf("%d", &up[i][0]);
    for (int j = 1; j < LOG; j++)
        for (int i = 1; i <= n; i++)
            up[i][j] = up[up[i][j - 1]][j - 1];

    while (q--) {
        int x, k;
        scanf("%d%d", &x, &k);
        for (int j = 0; j < LOG; j++)
            if (k & (1 << j))
                x = up[x][j];
        printf("%d\n", x);
    }
}

CSES Planets Queries II

Problem. \(Q\) queries of the form \((a, b)\): find the minimum number of teleportations to get from planet \(a\) to planet \(b\), or report that it's impossible.

This is harder. Three cases:

  1. \(a\) and \(b\) are on the same tail, with \(a\) before \(b\). Answer = distance along the tail.
  2. \(a\) is on a tail and \(b\) is on the cycle that \(a\)'s tail feeds into. Answer = tail distance to cycle + distance around cycle.
  3. Otherwise: impossible (\(b\) is on a different component, or \(b\) is on the tail before \(a\)).

Implementation outline:

  1. Find all cycles. For each node, record whether it's on a cycle and which cycle.
  2. For each node, compute its distance to the cycle.
  3. For tail nodes, find which cycle node they first reach.
  4. For queries on the same cycle, compute distance using cycle length.

We'll use binary lifting for step (4): jump from \(a\) forward and check if we reach \(b\).

Gotcha. If \(a\) is on a cycle and \(b\) is on a tail, the answer is always -1. You can only move forward in a functional graph, and once you're on a cycle you stay on the cycle.

When Binary Lifting Meets Trees

Binary lifting for successor queries is the functional-graph analogue of binary lifting for LCA in trees. In trees, \(\text{up}[x][j]\) is the \(2^j\)-th ancestor. In functional graphs, it's the \(2^j\)-th successor. Same table, same query decomposition, different graph.

If you've already learned LCA with binary lifting, this lesson is pure pattern matching.

Complexity

Operation Time Space
Precomputation \(O(N \log K)\) \(O(N \log K)\)
Single query \(O(\log K)\) --

For \(N = 2 \times 10^5\) and \(K = 10^9\): \(\log K = 30\). Precomputation = \(6 \times 10^6\) operations. Each query = 30 operations. Both trivially fast.

Problems

Problem Link Difficulty
CSES Planets Queries I cses.fi/problemset/task/1750 Medium
CSES Planets Queries II cses.fi/problemset/task/1160 Hard