Heavy-Light Decomposition

Splitting a tree into chains so that any root-to-node path crosses only logarithmically many chains, enabling fast path queries.

Turning trees into arrays

Heavy-light decomposition (HLD) partitions the edges of a rooted tree into heavy and light so that every path from any node to the root passes through at most O(log n) light edges. This lets path queries and updates on a tree reduce to a few contiguous range operations on an array, handled by a segment tree.

Heavy and light edges

Kronos motion — heavy industry

For each node, the edge to the child with the largest subtree is the heavy edge; all others are light. Following heavy edges forms chains. Because each light edge at least halves the remaining subtree size, any root path crosses at most log n light edges, so it touches at most log n chains.

Path query

python

def path_query(u, v, seg, head, pos, depth, parent):
    res = IDENTITY
    while head[u] != head[v]:
        if depth[head[u]] < depth[head[v]]:
            u, v = v, u
        res = combine(res, seg.query(pos[head[u]], pos[u]))
        u = parent[head[u]]
    if depth[u] > depth[v]:
        u, v = v, u
    res = combine(res, seg.query(pos[u], pos[v]))
    return res

Cost

A path query or update walks at most O(log n) chains, each handled by one O(log n) segment-tree operation, so each path operation is O(log^2 n). Preprocessing is two depth-first traversals in O(n): one to compute subtree sizes and pick heavy children, one to lay chains contiguously in an array.

Uses

Path sum, max, or assignment between any two nodes.
Subtree queries, since each subtree is a contiguous range in the layout.
Combined with LCA for distance and path-splitting.
An alternative to link-cut trees for static-topology trees.