Path queries on trees
Heavy light decomposition lets you answer queries along the path between two nodes in a tree, such as the maximum edge or the sum of values, in roughly logarithmic time squared. It does this by splitting the tree into chains that map cleanly onto an array backed by a segment tree.
Heavy and light edges
For each node, the child whose subtree is largest is its heavy child; the edge to it is a heavy edge. All other child edges are light. Following heavy edges links nodes into vertical chains. The key fact: any root to node path crosses at most a logarithmic number of light edges, so it spans only a logarithmic number of chains.
Querying a path
- Lay the chains out contiguously so each chain is a range in one array.
- Build a segment tree over that array.
- To query the path between two nodes, repeatedly jump up by whole chains toward their lowest common ancestor, querying each chain segment, until both nodes share a chain.
Key idea
Decompose the tree into heavy chains placed contiguously in an array, so any path splits into a logarithmic number of segment tree queries.