Heavy-Light Decomposition (HLD): Decomposing Trees into O(log N) Heavy Paths

1. Heavy vs Light Edges & The $\lfloor \log_2 N \rfloor$ Path-Partition Bound

For each node $u$ with children $c_1, c_2, \dots, c_k$, pick a child $c^*$ maximizing $\text{sz}[c^*]$. Call $(u, c^*)$ the heavy edge out of $u$, and all other edges $(u, c_i)$ ($c_i \neq c^*$) light edges.

2. Climbing Chains in queryPath(u, v) & Handling Edge Weights vs Vertex Weights

To query or update the path between $u$ and $v$, compare the chain heads $\text{head}[u]$ and $\text{head}[v]$:

• While $\text{head}[u] \neq \text{head}[v]$, pick whichever chain head is deeper (say $\text{depth}[\text{head}[u]] > \text{depth}[\text{head}[v]]$), query the contiguous segment $[\text{pos}[\text{head}[u]], \text{pos}[u]]$ in the Segment Tree, and jump $u \leftarrow \text{parent}[\text{head}[u]]$ across the light edge into the upper chain.
• Once $\text{head}[u] = \text{head}[v]$, $u$ and $v$ lie on the same heavy chain! Query the final segment $[\min(\text{pos}[u], \text{pos}[v]), \max(\text{pos}[u], \text{pos}[v])]$ (for vertex queries) or $[\min(\text{pos}[u], \text{pos}[v]) + 1, \max(\text{pos}[u], \text{pos}[v])]$ (when weights live on edges and each edge weight is stored at its deeper child endpoint, excluding the LCA vertex!).

3. Production Implementation: Heavy-Light Decomposition with Iterative Segment Tree

/**
 * Heavy-Light Decomposition (HLD) supporting:
 *  - Point update on vertex u: O(log N)
 *  - Path query between u and v: O(log^2 N)
 *  - Subtree query on u: O(log N)
 *  - LCA(u, v): O(log N)
 */
class HeavyLightDecomposition {
  constructor(n, adj, values, combine, identity, root = 0) {
    this.n = n;
    this.combine = combine;
    this.identity = identity;

    this.parent = new Int32Array(n);
    this.depth = new Int32Array(n);
    this.sz = new Int32Array(n);
    this.heavy = new Int32Array(n).fill(-1);
    this.head = new Int32Array(n);
    this.pos = new Int32Array(n);

    this._dfsSize(adj, root);
    this._dfsDecompose(adj, root);

    // Build flat 2N iterative segment tree in HLD pos[] order
    this.tree = new Array(2 * n);
    for (let u = 0; u < n; u++) {
      this.tree[n + this.pos[u]] = values[u];
    }
    for (let i = n - 1; i >= 1; i--) {
      this.tree[i] = combine(this.tree[i << 1], this.tree[(i << 1) | 1]);
    }
  }

  _dfsSize(adj, root) {
    const order = [root];
    this.parent[root] = -1;
    this.depth[root] = 0;
    for (let i = 0; i < order.length; i++) {
      const u = order[i];
      for (const v of adj[u]) {
        if (v !== this.parent[u]) {
          this.parent[v] = u;
          this.depth[v] = this.depth[u] + 1;
          order.push(v);
        }
      }
    }
    for (let i = order.length - 1; i >= 0; i--) {
      const u = order[i];
      this.sz[u] = 1;
      let maxSub = 0;
      for (const v of adj[u]) {
        if (v !== this.parent[u]) {
          this.sz[u] += this.sz[v];
          if (this.sz[v] > maxSub) {
            maxSub = this.sz[v];
            this.heavy[u] = v;
          }
        }
      }
    }
  }

  _dfsDecompose(adj, root) {
    let curPos = 0;
    const stack = [[root, root]]; // [u, chainHead]
    while (stack.length > 0) {
      const [u, h] = stack.pop();
      this.head[u] = h;
      this.pos[u] = curPos++;
      // Push light children first so heavy[u] is popped and visited FIRST!
      for (let i = adj[u].length - 1; i >= 0; i--) {
        const v = adj[u][i];
        if (v !== this.parent[u] && v !== this.heavy[u]) {
          stack.push([v, v]);
        }
      }
      if (this.heavy[u] !== -1) {
        stack.push([this.heavy[u], h]);
      }
    }
  }

  _segQuery(l, r) {
    let resL = this.identity, resR = this.identity;
    for (let a = l + this.n, b = r + this.n + 1; a < b; a >>= 1, b >>= 1) {
      if (a & 1) resL = this.combine(resL, this.tree[a++]);
      if (b & 1) resR = this.combine(this.tree[--b], resR);
    }
    return this.combine(resL, resR);
  }

  setVertex(u, val) {
    let p = this.pos[u] + this.n;
    this.tree[p] = val;
    for (p >>= 1; p >= 1; p >>= 1) {
      this.tree[p] = this.combine(this.tree[p << 1], this.tree[(p << 1) | 1]);
    }
  }

  queryPath(u, v) {
    let res = this.identity;
    while (this.head[u] !== this.head[v]) {
      if (this.depth[this.head[u]] < this.depth[this.head[v]]) {
        const tmp = u; u = v; v = tmp;
      }
      res = this.combine(res, this._segQuery(this.pos[this.head[u]], this.pos[u]));
      u = this.parent[this.head[u]];
    }
    if (this.depth[u] > this.depth[v]) {
      const tmp = u; u = v; v = tmp;
    }
    return this.combine(res, this._segQuery(this.pos[u], this.pos[v]));
  }

  querySubtree(u) {
    return this._segQuery(this.pos[u], this.pos[u] + this.sz[u] - 1);
  }
}

4. Complexity Matrix