---
title: "Heavy-Light Decomposition"
summary: Path queries with updates in O(log^2 n) — the decomposition, why light edges are few, the segment tree layout, and lazy propagation on chains.
difficulty: hard
tags: [trees, segment tree, paths, queries]
time: n pre, log^2 n query
space: n
prereq: [structures/segment-tree, trees/euler-tour, lca/hld-lca]
see: [structures/segment-tree, lca/hld-lca]
demo: hld
---

## Chains: heavy and light

:::definition label="The decomposition"
Root the tree. For each vertex, the **heavy child** is the child with the largest subtree; all other children are *light*. The **heavy paths** are the maximal chains obtained by always following the heavy child. Store for each vertex: `head[v]` (top of its chain), `pos[v]` (index in the base array), obtained by a DFS that visits the heavy child **first**.
:::

:::theorem title="At most log n light edges per root path"
On any path from the root to a leaf there are at most $\log_2 n$ light edges, hence any root-to-vertex path meets at most $\log_2 n + 1$ chains, and any $u$–$v$ path meets at most $2\log_2 n + 1$.
:::

:::proof
If $(p, c)$ is light then $\operatorname{size}(c) < \tfrac12 \operatorname{size}(p)$: $p$'s heavy child has the largest subtree, so if a light child had more than half, the heavy one would have less than the light one — contradiction. Walking upward from any vertex, each light edge at least doubles the subtree size, and sizes are bounded by $n$, so there are $\le \log_2 n$ of them. A $u$–$v$ path is two root paths minus their common prefix. ∎
:::

## Implementation

```cpp hld.cpp
// ---- build: two DFS, both O(n) ----
int sub[n], dep[n], par[n], head[n], pos[n], timer;
int dfs_sz(int v, int p) {
    sub[v] = 1; par[v] = p; int best = -1, bestsz = 0;
    for (int to : g[v]) if (to != p) {
        dep[to] = dep[v] + 1;
        int s = dfs_sz(to, v); sub[v] += s;
        if (s > bestsz) { bestsz = s; best = to; }
    }
    if (best != -1) head[best] = head[v];           // heavy child continues the chain
    return sub[v];
}
void dfs_decompose(int v) {                        // heavy child FIRST -> chain is contiguous
    pos[v] = timer++;
    int best = -1, bestsz = 0;
    for (int to : g[v]) if (to != par[v] && sub[to] > bestsz) { bestsz = sub[to]; best = to; }
    if (best != -1) dfs_decompose(best);
    for (int to : g[v]) if (to != par[v] && to != best) { head[to] = to; dfs_decompose(to); }
}
// usage: head[v] initialised to v before dfs_sz for the root, and to the child itself otherwise.

// ---- query: walk chains bottom-up ----
int path_query(int u, int v) {                     // sum of values on the path u-v
    int res = 0;
    while (head[u] != head[v]) {
        if (depth[head[u]] < depth[head[v]]) swap(u, v);
        res += seg.query(pos[head[u]], pos[u]);    // [head..u] is contiguous!
        u = par[head[u]];
    }
    if (depth[u] > depth[v]) swap(u, v);
    res += seg.query(pos[u], pos[v]);              // same chain: include the LCA once
    return res;
}
```

## What it buys you

:::props title="The four things you can now do"
- **path query / path update** (sum, max, min, count-of-Z, xor…): $O(\log^2 n)$ with a segment tree over `pos` — @structures/segment-tree for the tree itself,
- **edge weights**: store each edge's value at its **deeper endpoint**, then a path query becomes $\operatorname{query}(\text{pos}[lca]+1, \text{pos}[x])$ — the "$+1$" is the single most common HLD bug,
- **subtree query / update**: `pos` order from a heavy-first DFS is still a DFS order, so a subtree is an interval $[\operatorname{pos}[v], \operatorname{pos}[v] + \operatorname{sub}[v])$ — the same as @trees/euler-tour, so HLD gives both path *and* subtree intervals for free,
- **LCA** in the same loop (@lca/hld-lca), and **k-th vertex on a path** by descending chain by chain with lengths.
:::

:::note title="Why O(log^2 n) and why people still ship it"
$\log n$ chains × $O(\log n)$ segment-tree work each. The $\log$ from the tree is *cache-friendly and small*; in practice 3–5 chains per path, so the loop body runs a handful of times. A "top tree / link-cut tree" achieves $O(\log n)$ but costs 100+ lines and a debugging session you will not finish in a contest. HLD is the correct complexity/performance trade for a contest, and the standard answer in interviews when asked "how would you support path sums with updates".
:::

## Failure modes

:::warning title="The five failure modes"
1. **Heavy child by depth, not by subtree size** — the bound dies (a "broom" tree gives $\Theta(n)$ chains per path).
2. **`dfs_decompose` visiting children in input order** instead of heavy-first — then a chain is *not* contiguous and every path query silently returns garbage on chains of length ≥ 3.
3. **Forgetting `head[heavy_child] = head[v]`** (the chain-extension line) — you then get one chain per vertex, i.e. $O(n)$ per query with the "correct" asymptotics on paper.
4. **Including the LCA twice** on a vertex-weighted path, or **omitting it** on an edge-weighted one;
5. **Recursion depth** $n$ in both DFSs: iterative or raise the stack (@foundations/walks), because HLD instances are usually $n \le 10^5$–$10^6$ *and* adversarial (paths, stars).
:::

:::demo id="hld" caption="Chain colours, and the query walk: the two endpoints leap head-by-head until they share a chain. Notice how few chains a path crosses even on this tree — that is the log n bound being generous."
:::

## Two named reductions

:::props title="Two reductions worth knowing by name"
- **Max/min edge on a path, with edge updates** (the classic *Query on a tree*): store edge weights at the deeper endpoint, query $\max$ over $[\operatorname{pos}[lca]+1, \operatorname{pos}[x]]$, update by point-assigning at $\operatorname{pos}[c]$.
- **Path painting + counting runs of a colour**: keep `(first, last, runs)` per segment tree node with a lazy colour tag; HLD supplies the intervals. Same shape as @structures/segment-tree's lazy example, one more field.
:::

:::problems
- [[SPOJ QTREE]] Query on a tree | https://www.spoj.com/problems/QTREE/ | hard | max edge on a path with updates — the benchmark for HLD
- [[CSES 1135]] Distance Queries | https://cses.fi/problemset/task/1135 | core | solve with HLD's lca to compare code size against lifting
- [[CSES 1137]] Subtree Queries | https://cses.fi/problemset/task/1137 | easy | the interval half of the same machinery
:::