Heavy-Light Decomposition

How HLD works

A query like "sum the edge weights on the path from node u to node v" on a tree of N nodes is a chore. Walk one node at a time and you pay O(N) per query. Lift via binary jumps and you get LCA in O(log N), but visiting every edge on a 10⁵-node path is still O(N). HLD breaks that by carving the tree into chains — contiguous paths that a 1D segment tree can handle natively — and bounding the number of chains any path crosses.

Run a first DFS to compute subtree sizes. For each non-leaf node, mark the child with the largest subtree as heavy; the rest are light. Now run a second DFS that always descends into the heavy child first and assigns each node a position in a flat array. The key fact: nodes connected by heavy edges land contiguously. A heavy chain is a contiguous range of the flat array.

Why log N chains? Stepping across a light edge from a node to a child means the child's subtree is at most half the parent's (because a heavier sibling exists). So any root-to-leaf walk traverses at most log₂ N light edges — equivalently, switches between chains at most log₂ N times.

For a path query from u to v: walk both endpoints toward the LCA, jumping along whole heavy chains at a time. Each chain segment is a contiguous range — query the segment tree in O(log N). The path crosses at most 2 log N chains, total time O(log² N).

Worked example

Take a 15-node tree rooted at 1, with subtree-sized children selected as heavy. Suppose chains end up as:

Chain A: 1 — 2 — 4 — 8  (root chain)
Chain B: 3 — 5 — 9
Chain C: 6
Chain D: 7 — 10 — 11
Chain E: 12, 13, 14, 15  (singletons)

A path query from node 8 to node 11 climbs:

• 8 is in chain A. 11 is in chain D. Head of chain D is 7; jump 11 → 10 → 7 (segment-tree query on chain D's range).
• 7's parent is 1, which is in chain A. Now both endpoints are in chain A.
• Within chain A: query from 8 up to where 7's parent (1) joined → segment-tree query on chain A's range covering [pos(1), pos(8)].

Two chain crossings, three segment-tree queries each O(log N) — total ~3 × 17 = ~50 array touches for N = 10⁵, versus 10⁵ for naive path walking.

When to use HLD

• Path sum, max, min, or any associative aggregate between two tree nodes.
• Path updates — add δ to every node or edge on the path from u to v.
• Subtree queries — a single segment-tree range, O(log N).
• LCA via the chain heads, alongside binary-lifting LCA when needed.
• Network analysis: shortest path between two routers in a tree topology, sum of latencies, max-bottleneck edge.
• Phylogenetic distance queries in gene trees.

Avoid HLD when the tree itself mutates frequently (use link-cut trees) or when you only need subtree queries (DFS-order + segment tree is enough without the heavy/light distinction).

HLD vs centroid decomposition vs link-cut tree

	HLD	Centroid decomposition	Link-cut tree
Path query	O(log² N)	O(log N) (with augmentation)	O(log N) amortised
Subtree query	O(log N)	O(log² N) (per-centroid)	O(log N) amortised
Tree mutation	No (static)	No (static)	Yes (link, cut, re-root)
Build	O(N)	O(N log N)	O(N)
Memory	O(N)	O(N log N) typical	O(N)
Code length	~80 lines	~60 lines	~200 lines
Constant factor	Small	Medium	Large (splay trees)

HLD is the right choice when the tree is fixed, queries dominate, and you need rich segment-tree operations on the path.

Pseudo-code

// Pass 1: subtree sizes, heavy child
function dfsSize(u, parent):
    size[u] = 1
    heavyChild[u] = -1
    maxChild = 0
    for v in children(u):
        if v == parent: continue
        dfsSize(v, u)
        size[u] += size[v]
        if size[v] > maxChild:
            maxChild = size[v]
            heavyChild[u] = v

// Pass 2: assign chain heads + flat positions (Euler-like)
function dfsHLD(u, parent, head):
    pos[u] = nextPos++
    chainHead[u] = head
    if heavyChild[u] != -1:
        dfsHLD(heavyChild[u], u, head)
    for v in children(u):
        if v != parent and v != heavyChild[u]:
            dfsHLD(v, u, v)

// Path query u → v
function pathQuery(u, v):
    res = 0
    while chainHead[u] != chainHead[v]:
        if depth[chainHead[u]] < depth[chainHead[v]]: swap(u, v)
        res = combine(res, segQuery(pos[chainHead[u]], pos[u]))
        u = parent[chainHead[u]]
    if depth[u] > depth[v]: swap(u, v)
    res = combine(res, segQuery(pos[u], pos[v]))
    return res

JavaScript implementation

class HLD {
  // tree: adjacency list (0-indexed), values: per-node weight
  constructor(tree, values) {
    this.n = tree.length;
    this.tree = tree;
    this.parent = new Int32Array(this.n);
    this.depth = new Int32Array(this.n);
    this.size = new Int32Array(this.n);
    this.heavy = new Int32Array(this.n).fill(-1);
    this.head = new Int32Array(this.n);
    this.pos = new Int32Array(this.n);
    this.flat = new Int32Array(this.n);
    this._dfsSize(0, -1, 0);
    let counter = { c: 0 };
    this._dfsHLD(0, 0, counter);
    for (let i = 0; i < this.n; i++) this.flat[this.pos[i]] = values[i];
    this._buildSeg();
  }

  _dfsSize(u, p, d) {
    this.parent[u] = p; this.depth[u] = d; this.size[u] = 1;
    let maxC = 0;
    for (const v of this.tree[u]) {
      if (v === p) continue;
      this._dfsSize(v, u, d + 1);
      this.size[u] += this.size[v];
      if (this.size[v] > maxC) { maxC = this.size[v]; this.heavy[u] = v; }
    }
  }

  _dfsHLD(u, h, c) {
    this.head[u] = h; this.pos[u] = c.c++;
    if (this.heavy[u] !== -1) this._dfsHLD(this.heavy[u], h, c);
    for (const v of this.tree[u]) {
      if (v !== this.parent[u] && v !== this.heavy[u]) this._dfsHLD(v, v, c);
    }
  }

  // Trivial segment tree: sum + point update
  _buildSeg() {
    this.seg = new Int32Array(4 * this.n);
    const build = (node, l, r) => {
      if (l === r) { this.seg[node] = this.flat[l]; return; }
      const m = (l + r) >> 1;
      build(node * 2, l, m); build(node * 2 + 1, m + 1, r);
      this.seg[node] = this.seg[node * 2] + this.seg[node * 2 + 1];
    };
    build(1, 0, this.n - 1);
  }
  _segQuery(node, l, r, ql, qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return this.seg[node];
    const m = (l + r) >> 1;
    return this._segQuery(node * 2, l, m, ql, qr) + this._segQuery(node * 2 + 1, m + 1, r, ql, qr);
  }

  pathSum(u, v) {
    let res = 0;
    while (this.head[u] !== this.head[v]) {
      if (this.depth[this.head[u]] < this.depth[this.head[v]]) { const t = u; u = v; v = t; }
      res += this._segQuery(1, 0, this.n - 1, this.pos[this.head[u]], this.pos[u]);
      u = this.parent[this.head[u]];
    }
    if (this.depth[u] > this.depth[v]) { const t = u; u = v; v = t; }
    res += this._segQuery(1, 0, this.n - 1, this.pos[u], this.pos[v]);
    return res;
  }
}

// Example: linear tree 0-1-2-3-4 with weights [1,2,3,4,5]
const tree = [[1], [0,2], [1,3], [2,4], [3]];
const hld = new HLD(tree, [1, 2, 3, 4, 5]);
console.log(hld.pathSum(0, 4));   // 15

Python implementation — path max query

import sys
sys.setrecursionlimit(2 * 10**5 + 100)

class HLD:
    def __init__(self, tree, vals):
        n = self.n = len(tree)
        self.tree = tree
        self.parent = [-1] * n
        self.depth = [0] * n
        self.size = [1] * n
        self.heavy = [-1] * n
        self.head = [0] * n
        self.pos = [0] * n
        self.flat = [0] * n
        self._dfs_size(0, -1, 0)
        self._counter = 0
        self._dfs_hld(0, 0)
        for i in range(n): self.flat[self.pos[i]] = vals[i]
        self.seg = [0] * (4 * n)
        self._build(1, 0, n - 1)

    def _dfs_size(self, u, p, d):
        self.parent[u] = p; self.depth[u] = d
        max_c = 0
        for v in self.tree[u]:
            if v == p: continue
            self._dfs_size(v, u, d + 1)
            self.size[u] += self.size[v]
            if self.size[v] > max_c:
                max_c = self.size[v]; self.heavy[u] = v

    def _dfs_hld(self, u, h):
        self.head[u] = h; self.pos[u] = self._counter; self._counter += 1
        if self.heavy[u] != -1: self._dfs_hld(self.heavy[u], h)
        for v in self.tree[u]:
            if v != self.parent[u] and v != self.heavy[u]:
                self._dfs_hld(v, v)

    def _build(self, node, l, r):
        if l == r: self.seg[node] = self.flat[l]; return
        m = (l + r) // 2
        self._build(node * 2, l, m); self._build(node * 2 + 1, m + 1, r)
        self.seg[node] = max(self.seg[node * 2], self.seg[node * 2 + 1])

    def _query(self, node, l, r, ql, qr):
        if qr < l or r < ql: return float('-inf')
        if ql <= l and r <= qr: return self.seg[node]
        m = (l + r) // 2
        return max(self._query(node * 2, l, m, ql, qr),
                   self._query(node * 2 + 1, m + 1, r, ql, qr))

    def path_max(self, u, v):
        res = float('-inf')
        while self.head[u] != self.head[v]:
            if self.depth[self.head[u]] < self.depth[self.head[v]]: u, v = v, u
            res = max(res, self._query(1, 0, self.n - 1, self.pos[self.head[u]], self.pos[u]))
            u = self.parent[self.head[u]]
        if self.depth[u] > self.depth[v]: u, v = v, u
        return max(res, self._query(1, 0, self.n - 1, self.pos[u], self.pos[v]))

Variants

Weighted by edge value

Store each edge's weight at the deeper endpoint. Path queries become exactly the same code, except after walking both sides into a common chain you query from pos[u] + 1 to pos[v] — skip the LCA node because edges, not nodes, are aggregated.

Path updates with lazy segment trees

Promote the per-chain segment tree to support lazy add or assign. Path-add δ on (u, v) becomes the same chain-jump loop with segUpdate instead of segQuery. Cost stays O(log² N) per operation.

Euler tour + small-to-large

For static subtree queries with rich operations (e.g. distinct color count), HLD's flat positioning composes with small-to-large merging on the heavy child — DSU-on-tree. It avoids the per-chain segment tree at the cost of being offline.

Multiple segment trees

Some problems demand different aggregates per query type — keep one segment tree per aggregate (sum, max, count distinct via merge-sort-tree). Memory inflates but each query stays O(log² N).

Common bugs and edge cases

• Wrong endpoint chosen for swap. The chain-jump loop must always lift the deeper-head endpoint. Picking by node depth instead of chain-head depth desynchronises the two pointers and yields wrong sums.
• LCA off-by-one with edges. If weights live on edges, after both endpoints share a chain you query pos[u]+1..pos[v] not pos[u]..pos[v]. Forgetting to skip the LCA counts its parent edge twice (or once when it should be zero).
• Recursion depth on linear trees. A path-like tree of 10⁵ nodes blows JavaScript's stack. Convert dfsSize and dfsHLD to iterative variants or raise the recursion limit in Python.
• Heavy child tie-breaking. When two children have the same subtree size, pick deterministically — otherwise tests that rely on a specific chain head fail. Picking the lowest index works.
• Flat array misaligned with values. The segment tree indexes by flat position, not by node id. Copy vals[node] to flat[pos[node]] before building. Forgetting this gives garbage queries.
• Edge-vs-node ambiguity. Problems silently switch between "weights on edges" and "weights on nodes". Decide up front; the +1 offset and LCA skip depend on it.