# Implementing Binary Lifting for LCA and Ancestor Queries on Trees

> Implement binary lifting for efficient LCA and ancestor queries on trees. Preprocess in O(N log N) for O(log N) query time.

- Repository: [hzwer/shareoi](https://github.com/hzwer/shareoi)
- Tags: tutorial
- Published: 2026-03-03

---

**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

```cpp
#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

```python
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.