Heavy–Light Tree Decomposition
Break tree paths into a few contiguous heavy-chain intervals.
Free theory articleBreak tree paths into a few contiguous heavy-chain intervals.
Concept & interpretation
Heavy–Light Decomposition is a technique for answering path queries on trees by breaking the tree into contiguous heavy-chain intervals.
Experiment
Use the interactive module to trace paths between different nodes and see how the linear array is queried in disjoint intervals.
- Open the Interactive Module.
- Change the From node.
- Change the To node to observe how the path is broken into disjoint linear intervals.