Chapter 11 · Advanced Tree Algorithms
Heavy-Light Decomposition
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.
#Chains: heavy and light
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.
On any path from the root to a leaf there are at most log2 n light edges, hence any root-to-vertex path meets at most log2 n + 1 chains, and any u–v path meets at most 2log2 n + 1.
If (p, c) is light then size(c) < tfrac12 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 ≤ log2 n of them. A u–v path is two root paths minus their common prefix. ∎
#Implementation
// ---- 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
The four things you can now do
- path query / path update (sum, max, min, count-of-Z, xor…): O(log2 n) with a segment tree over
pos— Segment Tree for the tree itself, - edge weights: store each edge's value at its deeper endpoint, then a path query becomes query(pos[lca]+1, pos[x]) — the "+1" is the single most common HLD bug,
- subtree query / update:
posorder from a heavy-first DFS is still a DFS order, so a subtree is an interval [pos[v], pos[v] + sub[v]) — the same as Entry/Exit Times and the Euler Tour, so HLD gives both path and subtree intervals for free, - LCA in the same loop (LCA by Heavy-Light Decomposition), and k-th vertex on a path by descending chain by chain with lengths.
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
- Heavy child by depth, not by subtree size — the bound dies (a "broom" tree gives Θ(n) chains per path).
dfs_decomposevisiting 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.- 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. - Including the LCA twice on a vertex-weighted path, or omitting it on an edge-weighted one;
- Recursion depth n in both DFSs: iterative or raise the stack (Walks, Trails, Paths, Cycles), because HLD instances are usually n ≤ 105–106 and adversarial (paths, stars).
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
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 [pos[lca]+1, pos[x]], update by point-assigning at 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 Segment Tree's lazy example, one more field.