Path queries on a tree
You want to ask aggregate questions about the path between two nodes in a tree, and to update values along such paths. On a plain tree a path can wander across many branches, which is hard to summarize directly.
Heavy and light edges
Heavy light decomposition labels, at each node, the child with the largest subtree as the heavy child, and all other children as light. Following heavy edges from a node traces a downward chain. The tree is thus partitioned into chains linked by light edges.
The crucial property: any root to node path crosses only a small number of light edges, because each light edge steps into a subtree at most half as large. So a path between two nodes touches only a few chains.
Reducing paths to ranges
Lay each chain out contiguously and build a range structure, such as a segment tree, over that layout. A path query then breaks into:
- A handful of contiguous segments, one per chain the path covers.
- Each segment answered by the range structure.
Because the path spans few chains, the whole query is efficient, turning an awkward tree path into a few clean range queries.
Key idea
Split the tree into heavy chains so any path crosses few light edges, letting path queries become a few range queries.