Implementation in C++

Setting Up the Structure

To implement Binary Lifting, you need a few key data structures. First, the tree itself is typically represented using an adjacency list. This is a simple and efficient way to store the connections between nodes.

Next, we need the sparse table, which we'll call up. This 2D array is the core of Binary Lifting, where up[v][j] stores the $2^j$-th ancestor of node v. We also need an array to store the depth of each node, which is essential for LCA queries.

Finally, we'll define a constant for the maximum logarithm of the number of nodes. Since we're dealing with powers of two, we only need to store ancestors up to $2^{\lfloor \log_2 N \rfloor}$, where $N$ is the number of nodes.

#include <iostream>
#include <vector>
#include <cmath>

const int MAXN = 200005; // Maximum number of nodes
const int LOG_MAX = 18;  // ceil(log2(MAXN))

std::vector<int> adj[MAXN];
int up[MAXN][LOG_MAX];
int depth[MAXN];

In this setup, MAXN is a safe upper bound for the number of nodes in your tree. LOG_MAX is calculated based on this maximum. For 200,005 nodes, $\log_2(200005) \approx 17.6$ , so we use 18.

The Preprocessing Step

As you've learned, preprocessing builds the up table. This is done in two main phases. First, a single Depth First Search (DFS) or Breadth First Search (BFS) from the root node calculates the depth of every node and sets its immediate parent, which is its $2^0$-th ancestor.

// Depth First Search to set depths and immediate parents
void dfs(int v, int p, int d) {
    depth[v] = d;
    up[v][0] = p; // The 2^0-th ancestor is the parent

    for (int u : adj[v]) {
        if (u != p) {
            dfs(u, v, d + 1);
        }
    }
}

After the DFS populates up[v][0] for all v, we can fill the rest of the table. We use a nested loop to compute the $2^j$-th ancestor by leveraging the $2^{j-1}$-th ancestors that have already been computed. Remember, the $2^j$-th ancestor of v is the $2^{j-1}$-th ancestor of its $2^{j-1}$-th ancestor.

up[v][j] = up[up[v][j-1]][j-1]

// Function to run the full preprocessing
void preprocess(int n, int root) {
    // 1. Run DFS to fill depth and up[v][0]
    dfs(root, root, 0); // Assuming root is its own parent

    // 2. Fill the rest of the 'up' table
    for (int j = 1; j < LOG_MAX; ++j) {
        for (int i = 1; i <= n; ++i) {
            up[i][j] = up[up[i][j-1]][j-1];
        }
    }
}

Executing Queries

With the up table fully preprocessed, we can answer queries efficiently. To find the $k$ -th ancestor of a node v, we express k in its binary form and make jumps for each power of two present in k.

// Find the k-th ancestor of node v
int get_ancestor(int v, int k) {
    for (int j = LOG_MAX - 1; j >= 0; --j) {
        if (k & (1 << j)) { // If the j-th bit of k is set
            v = up[v][j];
        }
    }
    return v;
}

Finding the Lowest Common Ancestor (LCA) builds on this. First, we bring the two nodes, u and v, to the same depth. Then, we jump them up together until their parents are the same. Their common parent is the LCA.

// Find the LCA of nodes u and v
int lca(int u, int v) {
    // 1. Ensure u is deeper than v
    if (depth[u] < depth[v]) {
        std::swap(u, v);
    }

    // 2. Bring u to the same depth as v
    u = get_ancestor(u, depth[u] - depth[v]);

    // 3. If they are the same node, we're done
    if (u == v) {
        return u;
    }

    // 4. Jump up together until their parents are the same
    for (int j = LOG_MAX - 1; j >= 0; --j) {
        if (up[u][j] != up[v][j]) {
            u = up[u][j];
            v = up[v][j];
        }
    }

    // The parent of the final u is the LCA
    return up[u][0];
}

Debugging and Optimization

When implementing Binary Lifting, a few common issues can arise. One is an off-by-one error, especially when dealing with depths or the value of k. Always double-check your base cases, like when k=0 or when one node is an ancestor of the other in an LCA query.

Another pitfall is handling the root of the tree. The root's parent should be set to itself or a sentinel value (like 0 or -1) to prevent jumping outside the tree's bounds. In our dfs, we set up[root][0] = root, which works well.

For optimization, the value of LOG_MAX is important. If it's too small, you won't be able to answer queries for large k. If it's too large, you'll waste memory and preprocessing time. Calculating it as ceil(log2(N)) is the optimal approach. For competitive programming, setting it to a safe constant like 18 or 20 for $N \le 2 \cdot 10^5$ is standard practice.

Always test your implementation with edge cases: a line graph (a 'stick' tree), a star graph (one central node connected to all others), and a tree with only two nodes.

Finally, ensure your node indexing is consistent. Some problems use 1-based indexing, while others use 0-based. Our code uses 1-based indexing for nodes from 1 to n. Adjusting for 0-based indexing is a small but critical change.

Quiz Questions 1/5

In the context of Binary Lifting, what does the up[v][j] entry in the sparse table typically store?

Quiz Questions 2/5

After an initial DFS/BFS computes the depth and immediate parent (up[v][0]) for each node v, the rest of the up table is filled. What is the correct recurrence relation to compute up[v][j] for j > 0?

Now you have the complete picture of how to translate the theory of Binary Lifting into working C++ code. The combination of a DFS and a dynamic programming approach gives you a powerful tool for solving problems on trees.

Mastering Binary Lifting