Data Structures19 sections · 729 units
Open in Course

Heavy-Light Decomposition

Linearizing tree paths

Heavy-Light Decomposition (HLD) transforms tree path queries into at most O(log⁡n)O(\log n) range queries on arrays. Here's the trick: decompose the tree into "heavy" chains.

A heavy child is the child with the largest subtree. All other children are "light." Following heavy edges creates chains that cover the tree.

Any path from a node to the root crosses at most O(log⁡n)O(\log n) light edges. Since each chain is an array segment, you can use segment trees on each chain. This sounds complex, but the idea is simple: turn a tree path into a few array ranges.