Introduction

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)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)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)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)O(\log n). Combine the two logs and a path query or update costs O(log⁡2n)O(\log ^{2}n) total — a dramatic improvement over O(n)O(n).

Try It

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">Click two nodes to query the path sum. Orange edges and nodes belong to heavy chains touched by the query. Watch how few chain segments are needed.</p>
<div class="canvas-wrap">
  <canvas id="c" width="480" height="300"></canvas>
</div>
<div class="info" id="info">Select a start node.</div>
<div class="btns">
  <button id="resetBtn" type="button" class="ghost">Reset selection</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Heavy-Light Decomposition demo.
// Tree is fixed: 9 nodes (0-8), rooted at 0.
// Edges: 0-1(w4), 0-2(w3), 1-3(w2), 1-4(w7), 2-5(w1), 2-6(w5), 3-7(w6), 3-8(w9)
// Heavy child of each node = child with largest subtree size.

const N = 9;
const ROOT = 0;

// Adjacency list: [neighbor, edgeWeight]
const adj = [
  [[1,4],[2,3]],        // 0
  [[0,4],[3,2],[4,7]],  // 1
  [[0,3],[5,1],[6,5]],  // 2
  [[1,2],[7,6],[8,9]],  // 3
  [[1,7]],              // 4
  [[2,1]],              // 5
  [[2,5]],              // 6
  [[3,6]],              // 7
  [[3,9]]               // 8
];

// ── HLD preprocessing ──────────────────────────────────────────────────────
const parent = new Array(N).fill(-1);
const depth  = new Array(N).fill(0);
const sz     = new Array(N).fill(1);
const heavy  = new Array(N).fill(-1);   // heavy child
const head   = new Array(N).fill(0);    // chain head
const pos    = new Array(N).fill(0);    // position in flat array
const edgeW  = {};                      // edgeKey -> weight (u<v)

// Build edge-weight map
for (let u = 0; u < N; u++) {
  for (const [v, w] of adj[u]) {
    const k = Math.min(u,v) + ',' + Math.max(u,v);
    edgeW[k] = w;
  }
}
function ew(u, v) { return edgeW[Math.min(u,v)+','+Math.max(u,v)] || 0; }

// DFS1: compute parent, depth, subtree size, heavy child
function dfs1(u, p, d) {
  parent[u] = p; depth[u] = d; sz[u] = 1;
  let maxSz = 0;
  for (const [v] of adj[u]) {
    if (v === p) continue;
    dfs1(v, u, d + 1);
    sz[u] += sz[v];
    if (sz[v] > maxSz) { maxSz = sz[v]; heavy[u] = v; }
  }
}
dfs1(ROOT, -1, 0);

// DFS2: assign chain heads and flat positions
let curPos = 0;
function dfs2(u, h) {
  head[u] = h; pos[u] = curPos++;
  if (heavy[u] !== -1) dfs2(heavy[u], h);
  for (const [v] of adj[u]) {
    if (v === parent[u] || v === heavy[u]) continue;
    dfs2(v, v);   // start a new chain
  }
}
dfs2(ROOT, ROOT);

// Segment tree on node weights (we store edge weight on the deeper node)
// nodeVal[u] = weight of edge from parent[u] to u (0 for root)
const nodeVal = new Array(N).fill(0);
for (let u = 1; u < N; u++) nodeVal[u] = ew(u, parent[u]);

// Simple O(n) range sum for demo clarity (HLD guarantees O(log n) intervals)
function rangeSum(l, r, posToNode) {
  let s = 0;
  for (let i = l; i <= r; i++) s += nodeVal[posToNode[i]];
  return s;
}

// Build inverse pos map
const posToNode = new Array(N);
for (let u = 0; u < N; u++) posToNode[pos[u]] = u;

// ── Path query: returns {sum, segments: [[u,v], ...]} ────────────────────
function pathQuery(u, v) {
  let sum = 0;
  const segments = []; // each: {nodes: Set of nodes in this chain interval}
  while (head[u] !== head[v]) {
    if (depth[head[u]] < depth[head[v]]) { let t=u; u=v; v=t; }
    // u's chain head is deeper: process from head[u] to u
    const chainNodes = new Set();
    for (let x = head[u]; ; x = parent[x] === -1 ? -1 : (pos[x] <= pos[u] ? x : -1)) {
      // collect nodes in pos range [pos[head[u]], pos[u]]
      break;
    }
    for (let p = pos[head[u]]; p <= pos[u]; p++) chainNodes.add(posToNode[p]);
    sum += rangeSum(pos[head[u]], pos[u], posToNode);
    segments.push(chainNodes);
    u = parent[head[u]];
  }
  // same chain now
  if (depth[u] > depth[v]) { let t=u; u=v; v=t; }
  // range [pos[u]+1, pos[v]] (exclude LCA for edge-weight semantics, include if u===v)
  const lo = pos[u] + (u === v ? 0 : 1);
  const hi = pos[v];
  if (lo <= hi) {
    const chainNodes = new Set();
    for (let p = lo; p <= hi; p++) chainNodes.add(posToNode[p]);
    sum += rangeSum(lo, hi, posToNode);
    if (chainNodes.size > 0) segments.push(chainNodes);
  }
  return { sum, segments };
}

// ── Layout (fixed node positions for clarity) ────────────────────
const POS = [
  [240, 30],  // 0
  [140, 100], // 1
  [340, 100], // 2
  [80,  180], // 3
  [200, 180], // 4
  [290, 180], // 5
  [400, 180], // 6
  [40,  260], // 7
  [130, 260], // 8
];
const R = 18;

// ── Drawing ──────────────────────────────────────────────────────────
const canvas = document.getElementById('c');
const ctx = canvas.getContext('2d');

let sel1 = -1, sel2 = -1;
let highlightNodes = new Set();
let highlightEdges = new Set();  // "u,v" with u<v
let queryResult = null;

function edgeHighlighted(u, v) {
  return highlightEdges.has(Math.min(u,v)+','+Math.max(u,v));
}

function draw() {
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  // edges
  for (let u = 0; u < N; u++) {
    for (const [v] of adj[u]) {
      if (v <= u) continue;
      const isHeavy = heavy[u] === v || heavy[v] === u;
      const isHigh  = edgeHighlighted(u, v);
      ctx.beginPath();
      ctx.moveTo(POS[u][0], POS[u][1]);
      ctx.lineTo(POS[v][0], POS[v][1]);
      ctx.lineWidth = isHigh ? 4 : (isHeavy ? 3 : 1.5);
      ctx.strokeStyle = isHigh ? '#e07800' : (isHeavy ? '#457b9d' : '#b0bec8');
      ctx.setLineDash(isHeavy ? [] : [5,4]);
      ctx.stroke();
      ctx.setLineDash([]);
      // edge weight label
      const mx = (POS[u][0]+POS[v][0])/2, my = (POS[u][1]+POS[v][1])/2;
      ctx.fillStyle = isHigh ? '#e07800' : '#555';
      ctx.font = isHigh ? 'bold 11px system-ui' : '10px system-ui';
      ctx.textAlign = 'center'; ctx.textBaseline = 'middle';
      ctx.fillText(ew(u,v), mx + 7, my - 7);
    }
  }
  // nodes
  for (let u = 0; u < N; u++) {
    const [x,y] = POS[u];
    const isSel = u === sel1 || u === sel2;
    const isHigh = highlightNodes.has(u);
    ctx.beginPath(); ctx.arc(x, y, R, 0, 2*Math.PI);
    ctx.fillStyle = isSel ? '#1d3557' : (isHigh ? '#e07800' : '#e8eef3');
    ctx.strokeStyle = isSel ? '#1d3557' : (isHigh ? '#c05e00' : '#457b9d');
    ctx.lineWidth = isSel || isHigh ? 2.5 : 1.5;
    ctx.fill(); ctx.stroke();
    ctx.fillStyle = isSel || isHigh ? '#fff' : '#1d3557';
    ctx.font = 'bold 13px system-ui';
    ctx.textAlign = 'center'; ctx.textBaseline = 'middle';
    ctx.fillText(u, x, y);
  }
  // legend
  ctx.font = '10px system-ui'; ctx.textAlign = 'left'; ctx.textBaseline = 'middle';
  ctx.strokeStyle = '#457b9d'; ctx.lineWidth = 2.5; ctx.setLineDash([]);
  ctx.beginPath(); ctx.moveTo(8,288); ctx.lineTo(28,288); ctx.stroke();
  ctx.fillStyle = '#457b9d'; ctx.fillText('heavy edge', 32, 288);
  ctx.strokeStyle = '#b0bec8'; ctx.lineWidth = 1.5; ctx.setLineDash([5,4]);
  ctx.beginPath(); ctx.moveTo(110,288); ctx.lineTo(130,288); ctx.stroke();
  ctx.setLineDash([]);
  ctx.fillStyle = '#666'; ctx.fillText('light edge', 134, 288);
}
draw();

// ── Interaction ──────────────────────────────────────────────────────────
canvas.addEventListener('click', e => {
  const rect = canvas.getBoundingClientRect();
  const scaleX = canvas.width / rect.width;
  const scaleY = canvas.height / rect.height;
  const mx = (e.clientX - rect.left) * scaleX;
  const my = (e.clientY - rect.top)  * scaleY;
  let hit = -1;
  for (let u = 0; u < N; u++) {
    const dx = POS[u][0]-mx, dy = POS[u][1]-my;
    if (dx*dx+dy*dy <= (R+4)*(R+4)) { hit = u; break; }
  }
  if (hit === -1) return;
  if (sel1 === -1) {
    sel1 = hit; sel2 = -1;
    highlightNodes.clear(); highlightEdges.clear();
    document.getElementById('info').textContent = fmt('Node %sel1% selected. Now pick the destination node.', { sel1: sel1 });
  } else if (sel2 === -1 && hit !== sel1) {
    sel2 = hit;
    runQuery();
  }
  draw();
});

function runQuery() {
  const { sum, segments } = pathQuery(sel1, sel2);
  highlightNodes.clear(); highlightEdges.clear();
  // collect all highlighted nodes
  for (const seg of segments) for (const nd of seg) highlightNodes.add(nd);
  // highlighted edges: any edge (u,v) where both u,v in highlightNodes AND edge is on the path
  // We mark edges that connect consecutive nodes on the path (parent-child within highlighted set)
  for (const nd of highlightNodes) {
    if (parent[nd] !== -1 && highlightNodes.has(parent[nd])) {
      highlightEdges.add(Math.min(nd,parent[nd])+','+Math.max(nd,parent[nd]));
    }
  }
  const chainCount = segments.length;
  document.getElementById('info').textContent =
    fmt('Path %sel1% → %sel2%  |  Sum = %sum%  |  Chain segments touched: %chainCount% (≀ O(log n))', { sel1: sel1, sel2: sel2, sum: sum, chainCount: chainCount });
  console.log('HLD path', sel1, '->', sel2, '| sum:', sum, '| segments:', chainCount,
    '| nodes:', [...highlightNodes].join(','));
  draw();
}

document.getElementById('resetBtn').addEventListener('click', () => {
  sel1 = -1; sel2 = -1;
  highlightNodes.clear(); highlightEdges.clear();
  document.getElementById('info').textContent = 'Select a start node.';
  draw();
});
Result
Console

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

The Real Complexity

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

Preprocessing — O(n)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)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\log_{2} n times before exhausting the tree's n nodes. So any path from root to leaf crosses at most ⌊log⁡2\log_{2} n⌋ light edges, meaning it spans at most ⌊log⁡2\log_{2} n⌋ + 1 heavy chains.

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

  • Decompose the path into O(log⁡n)O(\log n) chain intervals.
  • For each interval, perform a range query on the underlying segment tree: O(log⁡n)O(\log n) per interval.
  • Total per query: O(log⁡n)O(\log n) · O(log⁡n)O(\log n) = O(log⁡2n)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)O(\log n) per operation, but those structures are significantly more complex to implement. For most competitive-programming tasks HLD's O(log⁡2n)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.

Where It Matters

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⁡2n)O(\log ^{2}n) after an O(n)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)O(\log n) amortized.

Conclusion

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)O(\log n) contiguous pieces. Hand those pieces to a segment tree and you have O(log⁡2n)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/heavy-light-decomposition/Content licensed under CC BY-NC 4.0.