Heavy-Light Decomposition — Path Queries on Trees

Why it matters

HLD enables efficient tree path queries. Understanding shapes advanced tree problems.

The architecture

Heavy child: subtree with most nodes.

Heavy edge to heavy child; others light.

Chain: consecutive heavy edges.

How it works end to end

Path query: split into segments on chains. Each segment is contiguous in chain array.

Segment tree per chain (or flattened tree): O(log n) per segment.

Total: O(log² n) per path query.