Heavy-Light Decomposition

Trees are everywhere in competitive programming and systems design: hierarchies, networks, parse trees. But trees resist the classic range-query tricks. A path between two nodes can zigzag unpredictably, and a naïve scan costs $O(n)$ per query.

Heavy-Light Decomposition (HLD) — introduced in the algorithmic folklore and popularized in competitive programming — fixes this with one elegant observation: classify each edge as heavy or light.

• A heavy edge from a node to its child is the one leading to the child with the largest subtree. Every non-leaf node has exactly one heavy child.
• All other edges are light.

Chain the heavy edges together and you get a collection of heavy chains that cover the entire tree. The crucial fact: any path from a node to the root crosses at most $O(\log n)$ light edges — because every time you cross a light edge upward, the subtree size at least doubles. This means any root-to-node path breaks into at most $O(\log n)$ contiguous chains.

Each chain is then linearized in a DFS order so it becomes a contiguous array range. A segment tree or Fenwick tree sitting on that flat array answers any range query in $O(\log n)$. Combine the two logs and a path query or update costs $O(\log ^{2}n)$ total — a dramatic improvement over $O(n)$.

The tree below has pre-assigned edge weights. Click any two nodes to query the path sum between them. The demo runs HLD, highlights each heavy chain segment it touches (in orange), and counts how many separate chain intervals the path decomposes into.

<p class="hint">{{hint}}</p>
<div class="canvas-wrap">
  <canvas id="c" width="480" height="300"></canvas>
</div>
<div class="info" id="info">{{select_start}}</div>
<div class="btns">
  <button id="resetBtn" type="button" class="ghost">{{reset_sel}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.canvas-wrap { width: 100%; overflow-x: auto; }
canvas { display: block; background: #f4f7fa; border-radius: 10px; border: 1px solid #d0dae3; cursor: pointer; max-width: 100%; }
.info { font-size: .95rem; font-weight: 600; margin: .55rem 0; min-height: 1.5em; color: #1d3557; white-space: pre-wrap; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui; padding: .42rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice that even on a long path the number of highlighted chain segments is small — at most $O(\log n)$. That is the guarantee that makes HLD fast regardless of the tree's shape.

Heavy-Light Decomposition is a solved, efficient technique — it belongs firmly in P. Here is why the complexity works out:

Preprocessing — $O(n)$:

• A single DFS computes subtree sizes and identifies the heavy child of each node.
• A second pass (or the same pass) assigns DFS-order positions, grouping heavy chains into contiguous array ranges.
• Total: two linear scans, $O(n)$ time and space.

The light-edge doubling argument: Suppose you walk from node v up to the root. Each time you leave a heavy chain via a light edge, you move to a node whose subtree is at least twice as large (because the heavy child already claimed the larger half). You can double at most $\log_{2}$ n times before exhausting the tree's n nodes. So any path from root to leaf crosses at most ⌊$\log_{2}$ n⌋ light edges, meaning it spans at most ⌊$\log_{2}$ n⌋ + 1 heavy chains.

Per-query cost — $O(\log ^{2}n)$:

• Decompose the path into $O(\log n)$ chain intervals.
• For each interval, perform a range query on the underlying segment tree: $O(\log n)$ per interval.
• Total per query: $O(\log n)$ · $O(\log n)$ = $O(\log ^{2}n)$.

Can we do better? Yes — using an Euler-tour + LCA approach or a top tree / link-cut tree you can get $O(\log n)$ per operation, but those structures are significantly more complex to implement. For most competitive-programming tasks HLD's $O(\log ^{2}n)$ is fast enough and far simpler to code correctly.

HLD is not about hardness — it is about the elegant insight that structure hiding inside a tree can be revealed by a single edge classification, reducing an apparently irregular problem to straightforward range queries. See also segment trees for the companion structure that handles the chain queries.

Any time you need to repeatedly query or update values along arbitrary paths in a tree, HLD is the go-to tool:

• Competitive programming: path-sum, path-max, path-XOR, and LCA (lowest common ancestor) queries are all solvable in $O(\log ^{2}n)$ after an $O(n)$ HLD preprocessing step.
• Network routing: in hierarchical network topologies, finding the bottleneck bandwidth on a path between two nodes maps directly to a path-minimum query.
• Version control and dependency graphs: querying the "distance" or accumulated weight along a dependency chain in a build system or package manager.
• Game trees and AI: maintaining dynamic values along game-state paths where branches can be updated and queried independently.
• Compiler symbol tables: in languages with nested scopes represented as trees, HLD-style chain linearization accelerates scope-range lookups.
• Database query plans: hierarchical query-plan trees often need accumulated cost estimates along execution paths.

HLD pairs naturally with segment trees for range queries. When the tree itself is dynamic (edges added or removed), the heavier link-cut tree generalization takes over, supporting the same operations in $O(\log n)$ amortized.

Heavy-Light Decomposition turns the messiness of tree paths into a clean sequence of range queries. The insight is disarmingly simple: call an edge heavy if it leads to the biggest subtree, chain the heavy edges, and any path shatters into at most $O(\log n)$ contiguous pieces. Hand those pieces to a segment tree and you have $O(\log ^{2}n)$ per query — fast enough for trees with millions of nodes.

The technique is solved — no open problem lurks here, just elegant engineering. But it is a perfect illustration of how the right classification of structure can transform an apparently hard problem into a composition of easy ones. Many of the deepest tools in algorithms work exactly this way: find a hidden regularity, make it explicit, and let simpler machinery do the rest.