Heavy-Light Decomposition

Decompose a tree into vertex-disjoint paths so that any root-to-leaf walk crosses at most $O(\log n)$ of them. Laying those paths out contiguously in an array turns tree path queries into $O(\log n)$ range queries.

The decomposition

For each vertex, call the child with the largest subtree its heavy child; the edge to it is a heavy edge, all others are light.

Key lemma. Any root-to-leaf path crosses at most ${\log }_{2}n$ light edges — because crossing a light edge at least halves the subtree size (the light child has $\le$ half the parent’s subtree, else it would be heavy).

Heavy edges chain into heavy paths. Number vertices so that each heavy path occupies a contiguous range of positions.

Implementation

vector<int> par, dep, sz, heavy, head, pos;
int curPos = 0;
 
int dfsSize(int v) {                                  // find heavy children
    sz[v] = 1;
    int maxSub = 0;
    for (int c : adj[v]) {
        if (c == par[v]) continue;
        par[c] = v; dep[c] = dep[v] + 1;
        int sub = dfsSize(c);
        sz[v] += sub;
        if (sub > maxSub) { maxSub = sub; heavy[v] = c; }
    }
    return sz[v];
}
 
void decompose(int v, int h) {                        // assign positions
    head[v] = h;
    pos[v] = curPos++;
    if (heavy[v] != -1) decompose(heavy[v], h);       // continue this chain FIRST
    for (int c : adj[v])
        if (c != par[v] && c != heavy[v]) decompose(c, c);
}

Recursing into the heavy child first is what makes each chain contiguous.

Path queries

long long queryPath(int u, int v) {
    long long res = IDENTITY;
    for (; head[u] != head[v]; v = par[head[v]]) {
        if (dep[head[u]] > dep[head[v]]) swap(u, v);
        res = combine(res, seg.query(pos[head[v]], pos[v]));
    }
    if (dep[u] > dep[v]) swap(u, v);
    res = combine(res, seg.query(pos[u], pos[v]));     // final chain
    return res;
}

$O(\log n)$ chains, each costing $O(\log n)$ in the segment tree → $O({\log }^{2}n)$ per query. Range updates work identically with a lazy segment tree.

Non-commutative operations

The loop above visits chain segments in an arbitrary order, which is fine for sum, min, gcd and other commutative merges. For non-commutative merges (matrix products, string concatenation) you must accumulate the two sides separately — one going up from $u$, one from $v$ — and reverse one of them at the end.

Subtree queries come free

Because decompose numbers each subtree contiguously (it is a DFS order), the subtree of $v$ is exactly [pos[v], pos[v] + sz[v] - 1]. So one HLD gives both path queries and subtree queries.

Edge values instead of vertex values

Store each edge’s value at its child endpoint, then exclude the LCA from path queries:

if (u == v) return IDENTITY;                    // no edges
res = combine(res, seg.query(pos[u] + 1, pos[v]));   // skip the LCA itself

Forgetting the +1 is the most common HLD bug.

HLD vs the alternatives

Need	Structure	Complexity
LCA only	binary lifting	$O(\log n)$
Path queries, static tree	binary lifting with aggregates	$O(\log n)$
Path queries and updates, static tree	HLD + lazy segtree	$O({\log }^{2}n)$
Subtree queries and updates	Euler tour + segment tree	$O(\log n)$
Tree changes (link/cut)	link-cut tree	$O(\log n)$ am.
Path counting / distance problems	centroid decomposition	$O(n\log n)$
Queries on a small vertex subset	virtual tree	$O(k\log n)$

HLD is the workhorse: static tree, path updates and queries, $O({\log }^{2}n)$, and about 60 lines.

Getting to $O(\log n)$

Using a sparse table per chain gives $O(\log n)$ queries for idempotent operations without updates. With updates, $O(\log n)$ requires link-cut trees or a global balanced BST over the chains — rarely worth the complexity.

See also: Centroid Decomposition · Euler Tour · Link-Cut Tree