Query Execution

Putting Preprocessing to Work

With the sparse table precomputed, we're ready to answer queries. The setup phase did the heavy lifting. Now, we can find a node's k-th ancestor or the Lowest Common Ancestor (LCA) of two nodes with remarkable speed.

Finding the k-th Ancestor

How do we find the 13th ancestor of a node? We could walk up the tree one parent at a time, but that's slow. Binary Lifting lets us take massive jumps. The key is to think of the number $k$ in terms of powers of two.

For example, $13$ in binary is $1101$ , which is $8 + 4 + 1$ , or $2^3 + 2^2 + 2^0$ . To find the 13th ancestor, we can make three jumps from our starting node: first an 8-step jump, then a 4-step jump, and finally a 1-step jump. Our precomputed table gives us exactly the information we need to make these leaps.

The general algorithm iterates through the powers of two, from largest to smallest. If the $i$ -th bit is set in the binary representation of $k$ (meaning $2^i$ is part of its sum), we jump $2^i$ steps up the tree from our current position.

// Function to find the k-th ancestor of node u
// 'up' is the precomputed sparse table: up[i][j] is the 2^j-th ancestor of i
// LOGN is the maximum power of 2 we need, floor(log2(N))

int get_ancestor(int u, int k) {
    // Iterate from the largest power of 2 down to 0
    for (int j = LOGN; j >= 0; --j) {
        // If k is greater than or equal to 2^j
        // (or equivalently, if the j-th bit of k is set)
        if (k & (1 << j)) {
            // Make the jump of 2^j steps
            u = up[u][j];
        }
    }
    return u;
}

Finding the Lowest Common Ancestor

The Lowest Common Ancestor (LCA) of two nodes, u and v, is the deepest node in the tree that is an ancestor to both. Finding the LCA is a classic problem with many applications, and Binary Lifting provides an elegant solution.

The strategy involves two main phases:

Level the Nodes: First, we need to bring both nodes to the same depth. If u is deeper than v, we find their depth difference, say d, and then find the d-th ancestor of u. Now both nodes are at the same level.
Ascend Together: With the nodes at the same depth, we lift them up simultaneously. We jump by the largest power of two that doesn't land them on the same node. We keep doing this for smaller powers of two. By always taking the largest possible jump without meeting, we ensure they get as close as possible to their meeting point. Their immediate parent will be the LCA.

If the two nodes are already at the same level and are the same node, then that node is their LCA.

Why does this work? By repeatedly finding the highest ancestors of u and v that are not the same, we bring u and v to be the direct children of the LCA. The final step is just to find the parent of either one.

// depth[i] is the depth of node i
// parent[i] is the direct parent of node i
// up[i][j] is the 2^j-th ancestor of i

int lca(int u, int v) {
    // Ensure u is the deeper node
    if (depth[u] < depth[v]) {
        swap(u, v);
    }

    // 1. Level the nodes: bring u to the same depth as v
    int diff = depth[u] - depth[v];
    u = get_ancestor(u, diff); // Using the function from before

    // If v was an ancestor of u, then v is the LCA
    if (u == v) {
        return u;
    }

    // 2. Ascend together
    // From largest power of two to smallest
    for (int j = LOGN; j >= 0; --j) {
        // If the 2^j-th ancestors are different, jump
        if (up[u][j] != up[v][j]) {
            u = up[u][j];
            v = up[v][j];
        }
    }

    // After the loop, u and v are direct children of the LCA.
    // So, the parent of u (or v) is the LCA.
    return parent[u];
}

Quiz Questions 1/4

To find the 10th ancestor of a node using binary lifting, which sequence of jumps based on powers of two would be made?

Quiz Questions 2/4

What is the primary goal of the first phase of the binary lifting algorithm for finding the Lowest Common Ancestor (LCA) of two nodes, u and v?

These two query types, finding the k-th ancestor and the LCA, form the foundation of how Binary Lifting is used in practice. The efficiency comes from turning a linear walk up the tree into a series of logarithmic jumps.

Mastering Binary Lifting

Mastering Binary Lifting

Query Execution

Putting Preprocessing to Work

Finding the k-th Ancestor

Finding the Lowest Common Ancestor