Chapter 97

Home

Refactoring: LCA with Binary Lifting

Precompute up[u][k] = the 2ᴷ-th ancestor of u. Then LCA becomes: lift u and v to same depth, then lift both together. O(N log N) preprocessing, O(log N) per query.

Before: O(N) Walk-Up

C++ — O(N) per LCA query

while (depth[u] > depth[v]) u = parent[u];
while (u != v) { u = parent[u]; v = parent[v]; }
// O(N) for deep trees

After: O(log N) Binary Lifting

C++ — LCA with binary lifting

struct LCA {
    vector> up;
    vector depth;
    int LOG;

    LCA(vector>& adj, int root, int n) {
        LOG = ceil(log2(n)) + 1;
        up.assign(n, vector(LOG, -1));
        depth.assign(n, 0);
        dfs(adj, root, -1);
    }

    void dfs(vector>& adj, int u, int p) {
        up[u][0] = p;
        for (int k = 1; k < LOG; k++)
            if (up[u][k-1] != -1)
                up[u][k] = up[up[u][k-1]][k-1];

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

    int lca(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);

        // Lift u to depth of v
        int diff = depth[u] - depth[v];
        for (int k = 0; k < LOG; k++)
            if (diff & (1 << k)) u = up[u][k];

        if (u == v) return u;

        for (int k = LOG - 1; k >= 0; k--)
            if (up[u][k] != up[v][k]) {
                u = up[u][k];
                v = up[v][k];
            }

        return up[u][0];
    }
};

// Preprocess: O(N log N). Query: O(log N).

Rust — LCA

struct LCA {
    up: Vec>,
    depth: Vec,
    log: usize,
}
impl LCA {
    fn lca(&self, mut u: usize, mut v: usize) -> usize {
        if self.depth[u] < self.depth[v] { swap(&mut u, &mut v); }
        let diff = self.depth[u] - self.depth[v];
        for k in 0..self.log {
            if diff & (1 << k) != 0 { u = self.up[u][k] as usize; }
        }
        if u == v { return u; }
        for k in (0..self.log).rev() {
            if self.up[u][k] != self.up[v][k] {
                u = self.up[u][k] as usize;
                v = self.up[v][k] as usize;
            }
        }
        self.up[u][0] as usize
    }
}

Key Takeaways