Implementing Binary Lifting for LCA and Ancestor Queries on Trees

Binary lifting preprocesses a rooted tree in O(N log N) time to answer lowest common ancestor (LCA) and k-th ancestor queries in O(log N) per query by storing 2^j-th ancestors in a dynamic programming table.

The educational repository hzwer/shareoi hosts the definitive slide deck 树上倍增_黄哲威.pdf (Tree Binary Lifting) which exhaustively details this classic competitive programming technique. This guide translates those algorithmic concepts into production-ready C++ and Python implementations, demonstrating exactly how to construct the ancestor table and resolve tree queries efficiently.

The Binary Lifting Technique

Binary lifting (also referred to as "tree-upward doubling") enables logarithmic-time jumps up a rooted tree. Instead of traversing parent pointers one by one, the method pre-computes jump pointers for every node at intervals of powers of two (1, 2, 4, 8...). This allows any ancestor query to be decomposed into a sum of these powers, processed in O(log N) time via bit manipulation.

Preprocessing: Building the Up-Table

The preprocessing phase constructs a 2D table up where up[v][i] represents the 2^i-th ancestor of node v. According to the implementation patterns in 树上倍增_黄哲威.pdf, the construction follows these steps:

• Initialization: Run a DFS or BFS from the root to populate depth[v] and the immediate parent up[v][0].
• Doubling: For each power i from 1 to LOG-1, apply the recurrence:
  up[v][i] = up[ up[v][i-1] ][i-1]
  This states that the 2^i-th ancestor is the 2^(i-1)-th ancestor of the 2^(i-1)-th ancestor.
• LOG sizing: Set LOG = ⌊log₂N⌋ + 1, ensuring the table covers any ancestor up to the tree height.

This table requires O(N log N) memory and is computed in O(N log N) time.

Query Algorithms

Lowest Common Ancestor Queries

To find the LCA of nodes u and v:

1. Equalize depths: If depth[u] < depth[v], swap the nodes. Lift u upward by depth[u] - depth[v] steps using the binary representation of the difference. If u becomes equal to v, return u.
2. Simultaneous lifting: Iterate i from LOG-1 down to 0. If up[u][i] != up[v][i], move both nodes up: u = up[u][i] and v = up[v][i].
3. Return parent: After the loop, the LCA is up[u][0] (or up[v][0]).

k-th Ancestor Retrieval

To find the k-th ancestor of node v:

• Decompose k into its binary representation. For each bit i that is set (where 2^i is a component of k), jump v to up[v][i].
• If at any point v becomes -1 (or null), the ancestor does not exist.
• Return the final v.

Complexity Analysis

Phase	Time Complexity	Space Complexity
Preprocessing	O(N log N)	O(N log N) for the up table
LCA Query	O(log N)	O(1) auxiliary
k-th Ancestor	O(log N)	O(1) auxiliary

These bounds make binary lifting ideal for static trees with frequent upward queries, as implemented in the hzwer/shareoi reference materials.

Production-Ready Implementations

The following classes mirror the exact logic described in 树上倍增_黄哲威.pdf and the repository's algorithmic standards.

C++17 Implementation

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

struct BinaryLifting {
    int LOG;                       // max power of two
    vector<int> depth;             // depth from root
    vector<vector<int>> up;        // up[v][i] = 2^i-th ancestor of v

    BinaryLifting(int n, const vector<vector<int>>& adj, int root = 1) {
        LOG = 1;
        while ((1 << LOG) <= n) ++LOG;
        depth.assign(n + 1, 0);
        up.assign(n + 1, vector<int>(LOG, -1));

        // DFS to fill depth and up[v][0]
        function<void(int,int)> dfs = [&](int v, int p) {
            up[v][0] = p;
            for (int i = 1; i < LOG; ++i)
                up[v][i] = up[v][i-1] == -1 ? -1 : up[ up[v][i-1] ][i-1];
            for (int to : adj[v])
                if (to != p) {
                    depth[to] = depth[v] + 1;
                    dfs(to, v);
                }
        };
        dfs(root, -1);
    }

    // lift node v by k steps upward
    int kthAncestor(int v, int k) const {
        for (int i = 0; i < LOG && v != -1; ++i)
            if (k & (1 << i)) v = up[v][i];
        return v;
    }

    // lowest common ancestor of a and b
    int lca(int a, int b) const {
        if (depth[a] < depth[b]) swap(a, b);
        // bring a to same depth as b
        a = kthAncestor(a, depth[a] - depth[b]);
        if (a == b) return a;
        for (int i = LOG-1; i >= 0; --i)
            if (up[a][i] != up[b][i]) {
                a = up[a][i];
                b = up[b][i];
            }
        return up[a][0];
    }

    // distance between two nodes
    int distance(int a, int b) const {
        int c = lca(a, b);
        return depth[a] + depth[b] - 2*depth[c];
    }
};

Python 3 Implementation

import sys
sys.setrecursionlimit(10**6)

class BinaryLifting:
    def __init__(self, n, adj, root=1):
        self.LOG = (n).bit_length()
        self.depth = [0] * (n + 1)
        self.up = [[-1] * self.LOG for _ in range(n + 1)]

        def dfs(v, p):
            self.up[v][0] = p
            for i in range(1, self.LOG):
                anc = self.up[v][i-1]
                self.up[v][i] = -1 if anc == -1 else self.up[anc][i-1]
            for to in adj[v]:
                if to != p:
                    self.depth[to] = self.depth[v] + 1
                    dfs(to, v)

        dfs(root, -1)

    def kth_ancestor(self, v, k):
        i = 0
        while k and v != -1:
            if k & 1:
                v = self.up[v][i]
            k >>= 1
            i += 1
        return v

    def lca(self, a, b):
        if self.depth[a] < self.depth[b]:
            a, b = b, a
        a = self.kth_ancestor(a, self.depth[a] - self.depth[b])
        if a == b:
            return a
        for i in range(self.LOG - 1, -1, -1):
            if self.up[a][i] != self.up[b][i]:
                a = self.up[a][i]
                b = self.up[b][i]
        return self.up[a][0]

    def distance(self, a, b):
        c = self.lca(a, b)
        return self.depth[a] + self.depth[b] - 2 * self.depth[c]

Both implementations follow the precise algorithmic structure documented in the 树上倍增_黄哲威.pdf slide deck available in the hzwer/shareoi repository.

Summary

• Binary lifting stores 2^i-th ancestors in a DP table up[v][i], enabling O(log N) upward jumps.
• Preprocessing requires O(N log N) time and space, computed via DFS and the doubling recurrence up[v][i] = up[up[v][i-1]][i-1].
• LCA queries work by first equalizing node depths, then simultaneously lifting both nodes from the highest power downward until their parents converge.
• k-th ancestor queries decompose k into binary and apply the corresponding jumps from the up table.
• The technique is static; it does not support dynamic tree modifications without recomputation.

Frequently Asked Questions

What is the memory overhead of binary lifting?

Binary lifting requires O(N log N) additional memory to store the up table. For a tree with 10^5 nodes, this typically requires approximately 20 * 10^5 integers (assuming LOG ≈ 17), which fits comfortably within standard memory limits for competitive programming (256MB–1GB).

Can binary lifting handle dynamic tree updates?

No. Binary lifting is designed for static trees where the parent-child relationships do not change after preprocessing. If the tree structure changes (e.g., edge insertions or deletions), the up table must be recomputed from scratch in O(N log N) time. For fully dynamic LCA, alternative data structures like Link-Cut Trees are required.

How do I determine the appropriate LOG value for my implementation?

Set LOG = floor(log2(N)) + 1, or in code, use (N).bit_length() (Python) or a while-loop doubling until (1 << LOG) > N (C++). This ensures the highest power of two covers the maximum possible tree height, allowing jumps up to the root from any node.

Is binary lifting faster than Euler Tour + Sparse Table for LCA?

Binary lifting answers queries in O(log N) time with O(N log N) preprocessing, while Euler Tour + Sparse Table achieves O(1) query time with O(N log N) preprocessing. However, binary lifting has a lower constant factor, simpler implementation, and naturally supports k-th ancestor queries, whereas Euler Tour + RMQ requires additional logic for ancestor jumps. For most competitive programming scenarios, binary lifting is preferred for its versatility and code clarity.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}