Binary Lifting (Jump Pointers)

Binary lifting is an extension topic beyond most interviews; it pays off in hard OAs and top-tier rounds that ask for many "k-th ancestor" or "lowest common ancestor" queries, or for following a pointer an astronomically large number of times.

The idea fits in one sentence: instead of walking k steps one at a time, precompute where you end up after 1, 2, 4, 8, ... steps, then combine the powers of two that make up k. Any jump of up to 2^L steps then costs O(L) table lookups.

Intuition

Write k in binary. To move 13 = 8 + 4 + 1 steps, jump 1, then 4, then 8 (the order does not matter because every jump is "follow the same pointer some number of times"). So you need, for every node x and every level j, the node up[j][x] reached after 2^j steps. The table fills itself by doubling:

up[0][x] = the next node (the parent, or next[x])
up[j][x] = up[j - 1][ up[j - 1][x] ]     2^j steps = 2^(j-1) steps, twice

The same doubling works for any quantity that can be combined along the way: the sum of weights along a jump (sum[j][x] = sum[j - 1][x] + sum[j - 1][up[j - 1][x]]), the minimum edge on a path, and so on. It is also the idea behind the sparse table, where level j stores the minimum of each block of length 2^j, and any range is covered by two overlapping blocks.

Lowest common ancestor. First lift the deeper node until both nodes are at the same depth (a k-th ancestor query). If they now coincide, that is the answer. Otherwise, try jumps from the largest level down, and jump both nodes whenever their ancestors at that level differ; this keeps them just below their lowest common ancestor, whose parent is then the answer.

When to use it in interviews / OAs

• "Find the k-th ancestor of a node" with many queries on a static tree.
• "Lowest common ancestor" with many queries, distances between tree nodes (depth[a] + depth[b] - 2 * depth[lca]), or path aggregates (maximum edge weight on a path).
• "Follow next[] m times" where m is up to 10^9 or 10^18, possibly accumulating a sum: functional graphs, a pointer that jumps around a circle, simulations with a deterministic next state.
• Static range minimum or maximum queries in O(1) after O(n log n) preprocessing (sparse table).

Template

k-th ancestor

class KthAncestor:
    def __init__(self, parent: list[int]):  # parent[root] == -1
        n = len(parent)
        self.levels = max(1, n.bit_length())  # 2^levels > n - 1 >= any depth
        self.up = [parent[:]]  # up[j][v] = 2^j-th ancestor of v, or -1
        for _ in range(1, self.levels):
            prev = self.up[-1]
            self.up.append([prev[prev[v]] if prev[v] != -1 else -1 for v in range(n)])

    def query(self, v: int, k: int) -> int:
        j = 0
        while k and v != -1:
            if k & 1:
                v = self.up[j][v] if j < self.levels else -1
            k >>= 1
            j += 1
        return v

Lowest common ancestor

class LCA:
    def __init__(self, parent: list[int]):
        n = len(parent)
        self.depth = [-1] * n
        for v in range(n):  # fill depths iteratively by walking up to a known node
            path, u = [], v
            while u != -1 and self.depth[u] == -1:
                path.append(u)
                u = parent[u]
            d = self.depth[u] if u != -1 else -1
            for w in reversed(path):
                d += 1
                self.depth[w] = d
        self.kth = KthAncestor(parent)

    def query(self, a: int, b: int) -> int:
        up = self.kth.up
        if self.depth[a] < self.depth[b]:
            a, b = b, a
        a = self.kth.query(a, self.depth[a] - self.depth[b])  # lift a to b's depth
        if a == b:
            return a
        for j in range(len(up) - 1, -1, -1):
            if up[j][a] != up[j][b]:  # still below the LCA: jump both
                a, b = up[j][a], up[j][b]
        return up[0][a]

Huge jump counts with an aggregated sum

Follow nxt m times from start and add the weight of every node you jump from. Each level stores a half-open sum (the weights of the 2^j nodes you leave), so consecutive jumps never double count:

def jump_sum(nxt: list[int], weight: list[int], start: int, m: int) -> tuple[int, int]:
    """Return (final node, sum of the weights of the m nodes jumped from)."""
    n = len(nxt)
    to, acc = nxt[:], weight[:]  # level 0: one step
    node, total = start, 0
    while m:
        if m & 1:
            total += acc[node]
            node = to[node]
        m >>= 1
        if m:  # build the next level: two jumps of the current size
            acc = [acc[x] + acc[to[x]] for x in range(n)]
            to = [to[to[x]] for x in range(n)]
    return node, total

This version builds levels on the fly for a single query in O(n log m). With many queries, store every level (O(n log m) memory) and answer each in O(log m).

Sparse table for range minimum

class SparseTableMin:
    def __init__(self, a: list[int]):
        self.t = [a[:]]  # t[j][i] = min of a[i : i + 2^j]
        j = 1
        while (1 << j) <= len(a):
            prev, half = self.t[-1], 1 << (j - 1)
            self.t.append([min(prev[i], prev[i + half]) for i in range(len(a) - (1 << j) + 1)])
            j += 1

    def query(self, l: int, r: int) -> int:
        """Minimum of a[l..r], inclusive, in O(1)."""
        j = (r - l + 1).bit_length() - 1  # largest block that fits
        return min(self.t[j][l], self.t[j][r - (1 << j) + 1])  # two blocks may overlap

Overlap is harmless for min, max and gcd (idempotent operations) but not for sums; use prefix sums for those.

Complexity

• Building the jump table: O(n log n) time and memory (O(n log m) for jumps of up to m steps).
• k-th ancestor: O(log k) per query. LCA: O(log n) per query.
• jump_sum: O(n log m) for one query as written.
• Sparse table: O(n log n) to build, O(1) per query; no updates.

Common pitfalls

• Too few levels. Use enough levels to cover the largest jump: about log2(n) for ancestors, about 60 for m up to 10^18.
• Missing sentinel. Jumping past the root must stay at -1 (or at the root, if that is how the problem defines it); never index with -1 in Python, which silently wraps around to the last element.
• Double counting in sums. Store half-open aggregates (the nodes you leave, not the node you arrive at).
• Updating the table in place while computing the next level: compute the new level from the previous one only.
• Recursion for depths. Trees can be paths of 10^5 nodes; compute depths iteratively (BFS order or the walk-up method above).
• Sparse table for sums. Overlapping blocks only work for idempotent operations.

Interview variations

• Kth ancestor of a tree node: the class above.
• Lowest common ancestor with many queries, distance between two nodes in a tree.
• Maximum or minimum edge on a tree path: store the path aggregate next to each jump pointer.
• Jumping on a cycle or functional graph a huge number of times: binary lifting, or detect the cycle and use modular arithmetic.
• Static range minimum queries: sparse table.
• Beyond typical interviews: LCA by Euler tour plus sparse table (O(1) per query) and heavy-light decomposition for path updates.