Pattern Reference
Heavy-Light Decomposition
"Decompose tree into heavy/light paths for path queries with segment tree. Path sum, max, min, update."
Loading...
Deep Dive Tutorial
HLD works by labeling each node with a DFS timestamp such that every heavy chain occupies a contiguous range in the timestamp array. Then "query path u to v" becomes: walk up from u and v to their LCA, querying the segment tree on each chain segment encountered. Since any path crosses at most O(log n) chains (each switch to a new chain at least doubles the chain's subtree size), total query time is O(log²n).
Heavy-Light Decomposition with segment tree
class HLD {
constructor(n, edges, values, root = 0) {
this.n = n; this.root = root;
this.adj = Array.from({length: n}, () => []);
for (const [u, v] of edges) { this.adj[u].push(v); this.adj[v].push(u); }
this.parent = new Array(n).fill(-1);
this.depth = new Array(n).fill(0);
this.subtreeSize = new Array(n).fill(1);
this.heavyChild = new Array(n).fill(-1);
this.chainTop = new Array(n).fill(0);
this.pos = new Array(n); // DFS timestamp
this.vals = values; // node values
this._dfs1(root, -1); // compute sizes, heavy children
this._timer = 0;
this._flatVals = new Array(n);
this._dfs2(root, root); // assign positions, build flat array
this._seg = new SegTree(this._flatVals); // build segment tree
}
_dfs1(u, p) {
this.parent[u] = p;
let maxSize = 0;
for (const v of this.adj[u]) {
if (v === p) continue;
this.depth[v] = this.depth[u] + 1;
this._dfs1(v, u);
this.subtreeSize[u] += this.subtreeSize[v];
if (this.subtreeSize[v] > maxSize) { maxSize = this.subtreeSize[v]; this.heavyChild[u] = v; }
}
}
_dfs2(u, top) {
this.chainTop[u] = top;
this.pos[u] = this._timer++;
this._flatVals[this.pos[u]] = this.vals[u];
if (this.heavyChild[u] !== -1) this._dfs2(this.heavyChild[u], top);
for (const v of this.adj[u]) {
if (v === this.parent[u] || v === this.heavyChild[u]) continue;
this._dfs2(v, v); // new chain starts at v
}
}
// Query max on path u → v
queryPath(u, v) {
let res = -Infinity;
while (this.chainTop[u] !== this.chainTop[v]) {
if (this.depth[this.chainTop[u]] < this.depth[this.chainTop[v]]) [u, v] = [v, u];
res = Math.max(res, this._seg.query(this.pos[this.chainTop[u]], this.pos[u]));
u = this.parent[this.chainTop[u]];
}
if (this.depth[u] > this.depth[v]) [u, v] = [v, u];
return Math.max(res, this._seg.query(this.pos[u], this.pos[v]));
}
update(u, val) { this._seg.update(this.pos[u], val); }
}Worked Problems
dumbbell
HLD key insight: Any path in a tree = O(log n) contiguous chain segments. Each time we jump to a new chain, the subtree size at least doubles, so at most O(log n) jumps.
When to use HLD:
- Path query on tree (max, sum, update) that can't be solved with simple DFS
- When you need a segment tree / Fenwick on tree paths
Simpler alternatives first:
- Single path between fixed endpoints: DFS/LCA
- Subtree queries: Euler tour + segment tree (no HLD needed)
- Path sum without updates: prefix sums from root
Related: Centroid decomposition (different decomposition, handles "all paths through centroid" queries), Link-cut trees (dynamic connectivity + path queries).
When to use HLD:
- Path query on tree (max, sum, update) that can't be solved with simple DFS
- When you need a segment tree / Fenwick on tree paths
Simpler alternatives first:
- Single path between fixed endpoints: DFS/LCA
- Subtree queries: Euler tour + segment tree (no HLD needed)
- Path sum without updates: prefix sums from root
Related: Centroid decomposition (different decomposition, handles "all paths through centroid" queries), Link-cut trees (dynamic connectivity + path queries).