---
title: "LCA by Heavy-Light Decomposition"
summary: Climbing chains instead of bits — same asymptotics, half the memory, and the same code you need for path queries.
difficulty: hard
tags: [hld, queries, trees]
time: n pre, log n query
space: n
prereq: [lca/problem, trees/euler-tour]
see: [advanced-tree/hld, structures/segment-tree]
---

:::definition label="Chain climbing"
Decompose the tree into vertex-disjoint **heavy paths** (each vertex continues the path of its largest-subtree child, @advanced-tree/hld), and store for each vertex its chain's head $h[v]$ and depth. Then:
:::

```cpp hld-lca.cpp
int lca(int u, int v) {
    while (h[u] != h[v]) {
        if (depth[h[u]] < depth[h[v]]) swap(u, v);
        u = parent[h[u]];           // jump whole chains, always the deeper head
    }
    return depth[u] < depth[v] ? u : v;
}
```

:::theorem title="O(log n) chains, without a log-size table"
Each time the loop replaces $u$ by $\operatorname{parent}(h[u])$, the subtree of the new $u$ has size at least twice the subtree of the old $u$'s chain head: $h[u]$ was a light child of its parent, and a light child has size $\le$ half its parent's. Hence at most $\log_2 n$ chain jumps.
:::

:::proof
$\operatorname{size}(h[u]) \le \tfrac12 \operatorname{size}(\operatorname{parent}(h[u]))$ because the parent's heavy child has the largest subtree, so any light child carries at most half of the parent's vertices (the parent itself is the remainder, making it strictly less than half + 1). Composing along the loop gives $\operatorname{size} \ge 2^{\#\text{jumps}}$, so the count is at most $\log_2 n$. Termination is clear (heads strictly ascend), and correctness is the invariant "the LCA is an ancestor of both current vertices": the deeper head cannot be above the LCA (an ancestor of $u$ that is deeper than $\operatorname{lca}$ is strictly below it), so jumping it is safe. ∎
:::

:::props title="Binary lifting vs. chain climbing"
- **Memory**: $O(n)$ vs $O(n \log n)$ — one array per vertex vs 20, the reason to prefer HLD when $n = 10^6$ and memory is tight;
- **Speed**: the loop usually runs 1–3 iterations on real trees (the $\log n$ bound is worst case), so it is *faster* than lifting for random trees and slower on adversarial "all-light" ones;
- **What lifting does that this cannot**: $k$-th ancestor, "jump $j$ steps", max-edge-on-path without a segment tree, functional graphs. Chain heads give you "the head" but not "the $j$-th up";
- **What HLD does that lifting cannot**: path aggregates with point updates (the chains are contiguous in `pos`, so a segment tree over them answers sum/max/min on a path), and subtree updates with lazy propagation;
- **Preprocess**: one DFS + one loop, both $O(n)$ — no table build, so HLD's total setup is linear vs $n\log n$.
:::

:::note title="So which one?"
If the problem is *only* LCA: binary lifting (shorter, self-contained, gives you `lift`). If it is LCA *plus* anything on paths: HLD, and use its `lca` as a by-product — writing both is 10 wasted lines. The hybrid "heavy-light + lifting on the chain forest" exists (jump between chains with lifting) but almost never wins in contests.
:::

:::exercise title="Two small exercises"
1. Modify `lca` above to return $\operatorname{dist}(u,v)$ in the same loop, using an additional `wsum[v]` = root-distance: which comparisons change?
2. Show that "climb the deeper head" can be replaced by "climb the head with larger `pos`" **only** if the HLD numbering assigns `pos` in DFS order along chains. Find a tree where the naive `pos` comparison is wrong.
:::