Sign in to watch this lesson
Advanced - Trees Ā· 4:52
Heavy-Light Decomposition
Every vertex marks the child with the largest subtree as heavy; a light child has at most half its parent's subtree, so any root path crosses at most log n light edges and touches at most log n heavy chains. A DFS that visits the heavy child first lays every chain, and every subtree, out as a contiguous block of one array, so one segment tree serves them all. A path query repeatedly lifts the chain with the deeper head, one range per chain, for O(log^2 n) per query; edge values are stored at the lower endpoint and the LCA's slot is skipped.
You will learn
- Compute subtree sizes and heavy children, and prove that a root path crosses at most log n light edges
- Assign head[v] and pos[v] with a heavy-child-first DFS so that chains and subtrees are contiguous in one array
- Answer path queries by lifting the chain with the deeper head, in O(log^2 n) with a segment tree
- Handle edge-weighted paths (values at the child, skip the LCA's position), lazy path updates and non-commutative operations