---
title: "LCA by Binary Lifting"
summary: The 12-line precomputation, the two-phase query, and the family of problems it solves beyond LCA.
difficulty: core
tags: [lifting, queries, trees]
time: n log n pre, log n query
space: n log n
prereq: [lca/problem, trees/euler-tour]
see: [directed/functional, advanced-tree/hld]
demo: lca
---

:::definition label="The table"
$\operatorname{up}[v][j] = $ the $2^j$-th ancestor of $v$. Then $\operatorname{up}[v][j] = \operatorname{up}[\operatorname{up}[v][j-1]][j-1]$ — "halfway up, then halfway again", which is the whole idea.
:::

```cpp binary-lifting.cpp
const int LOG = 20;                       // 2^20 > 10^6 vertices
vector<array<int, LOG>> up(n);
vector<int> depth(n);
void dfs(int v, int p) {
    up[v][0] = p == -1 ? v : p;
    for (int j = 1; j < LOG; j++) up[v][j] = up[up[v][j-1]][j-1];
    for (int to : g[v]) if (to != p) { depth[to] = depth[v] + 1; dfs(to, v); }
}
int lift(int v, int k) {                  // k-th ancestor of v (k <= depth[v])
    for (int j = 0; j < LOG; j++) if (k >> j & 1) v = up[v][j];
    return v;
}
int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    a = lift(a, depth[a] - depth[b]);     // phase 1: equalise depths
    if (a == b) return a;
    for (int j = LOG - 1; j >= 0; j--)    // phase 2: descend together
        if (up[a][j] != up[b][j]) { a = up[a][j]; b = up[b][j]; }
    return up[a][0];                      // one step above both
}
```

:::theorem title="Correctness"
After phase 1, $\operatorname{depth}(a) = \operatorname{depth}(b)$, and $\operatorname{lca}(a,b) = \operatorname{lca}(\text{original } a, \text{original } b)$ is unchanged (lifting an ancestor-side vertex to the other's depth cannot pass the LCA). In phase 2 the invariant is "$a$ and $b$ have equal depth and $\operatorname{lca}(a,b)$ is a proper ancestor of both"; each accepted jump preserves it, and after the loop $a$ and $b$ are the two children just below the LCA.
:::

:::proof
Phase 1: lifting $a$ to depth $\operatorname{depth}(b)$ keeps the LCA because $\operatorname{depth}(\operatorname{lca}) \le \operatorname{depth}(b)$, so we stop at or below it.
Phase 2: if $\operatorname{up}[a][j] \ne \operatorname{up}[b][j]$, both those ancestors are *strictly below* the LCA (otherwise, having equal depth and one common ancestor at that level, they would coincide) — so the jump cannot overshoot. Conversely, for every $j$ with $\operatorname{up}[a][j] = \operatorname{up}[b][j]$ the LCA is at or above that ancestor, so skipping those jumps loses nothing. Descending $j$ from $\text{LOG}-1$ to 0 therefore accumulates exactly $\operatorname{depth}(a) - \operatorname{depth}(\operatorname{lca}) - 1$ on each side. ∎
:::

:::note title="Iterate j from high to low, and say why"
Largest-jump-first is a *binary representation* greedy: $\text{depth difference} = \sum_j b_j 2^j$, so taking big jumps whenever they fit is exactly reading the bits. Low-to-high also works for `lift` (it is the same sum) but **not** for phase 2 — the invariant "still strictly below the LCA" is only maintained when you never overshoot, which requires descending powers. This asymmetry is the bug in most broken implementations.
:::

## Distances and the k-th vertex on a path
```cpp path-tools.cpp
int dist(int a, int b) { return depth[a] + depth[b] - 2 * depth[lca(a, b)]; }
// k-th vertex on the simple path a -> b (0 = a), k <= dist(a,b)
int kth_on_path(int a, int b, int k) {
    int c = lca(a, b), up_len = depth[a] - depth[c];
    return k <= up_len ? lift(a, k) : lift(b, dist(a, b) - k);
}
// vertex just below c on the path c -> x  (needed for "which subtree contains x"):
int below(int c, int x) { return lift(x, depth[x] - depth[c] - 1); }
```

:::props title="The same table answers far more"
- **$k$-th ancestor** / "who is $d$ steps up from $v$" — `lift`, $O(\log n)$,
- **diameter of a set** of vertices: lift-based farthest-pair queries reduce to $\max$ over a set with LCA distances,
- **jump through a functional graph** with cycle handling (@directed/functional) — identical code, `up[v][0] = f[v]`,
- **binary lifting on a dynamic DSU** ("successor after deletions", "the day two nodes became connected" — offline parallel binary search),
- **max edge on a path**: add a `mx[v][j]` array alongside `up`, combining with $\max$ — this is the same table, one more dimension, and it is the reason @advanced-tree/hld is only needed when updates are involved,
- **tree isomorphism-ish queries** and "is $u$ within distance $K$ of $v$" reduce to two lifts.
:::

:::demo id="lca" caption="Both phases visible: the depth-equalising lifts, then the pairs of jumps that stop one level below the answer. Toggle u and v to find a case where phase 2 does nothing."
:::

:::note title="When lifting loses"
$q \ge 10^6$ with a tight time limit: $O(\log n)$ per query is $2 \times 10^7$ random memory reads across a 14 MB table — cache-hostile. Euler+RMQ with $O(1)$ queries (@lca/rmq-lca) is faster there; Tarjan offline (@lca/tarjan-offline) is faster still when updates do not exist. Also: if the tree is a *path*, lifting degenerates to depth arithmetic — just use an array.
:::

:::problems
- [[CSES 1687]] Company Queries I | https://cses.fi/problemset/task/1687 | easy | k-th ancestor
- [[CSES 1688]] Company Queries II | https://cses.fi/problemset/task/1688 | core | LCA
- [[CSES 1135]] Distance Queries | https://cses.fi/problemset/task/1135 | core | dist via LCA
- [[CF 342E]] Xenia and Tree | https://codeforces.com/problemset/problem/342/E | hard | LCA inside centroid decomposition
:::