AntInLoop

Heavy-Light Decomposition (HLD) Code Implementations

Complete Heavy-Light Decomposition (HLD) code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.

Read Heavy-Light Decomposition (HLD) Guide ยท Launch Interactive Visualizer

CPP Implementation

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class HeavyLightDecomposition {
private:
    vector<vector<int>> adj;
    vector<int> parent, depth, size, heavy;
    vector<int> chain, pos;
    int chainCount, posCount;
    
    int dfs(int v, int p) {
        parent[v] = p;
        depth[v] = (p == -1) ? 0 : depth[p] + 1;
        size[v] = 1;
        heavy[v] = -1;
        
        int maxSize = 0;
        for (int u : adj[v]) {
            if (u != p) {
                int childSize = dfs(u, v);
                size[v] += childSize;
                if (childSize > maxSize) {
                    maxSize = childSize;
                    heavy[v] = u;
                }
            }
        }
        return size[v];
    }
    
    void decompose(int v, int chainId) {
        chain[v] = chainId;
        pos[v] = posCount++;
        
        if (heavy[v] != -1) {
            decompose(heavy[v], chainId);
        }
        
        for (int u : adj[v]) {
            if (u != parent[v] && u != heavy[v]) {
                decompose(u, ++chainCount);
            }
        }
    }
    
public:
    HeavyLightDecomposition(vector<vector<int>>& tree) : adj(tree) {
        int n = tree.size();
        parent.resize(n);
        depth.resize(n);
        size.resize(n);
        heavy.resize(n);
        chain.resize(n);
        pos.resize(n);
        
        chainCount = 0;
        posCount = 0;
        
        dfs(0, -1);
        decompose(0, 0);
    }
    
    int lca(int u, int v) {
        while (chain[u] != chain[v]) {
            if (depth[chain[u]] > depth[chain[v]]) {
                u = parent[chain[u]];
            } else {
                v = parent[chain[v]];
            }
        }
        return depth[u] < depth[v] ? u : v;
    }
    
    void printDecomposition() {
        cout << "Heavy-Light Decomposition:" << endl;
        for (int i = 0; i <= chainCount; i++) {
            cout << "Chain " << i << ": ";
            for (int j = 0; j < adj.size(); j++) {
                if (chain[j] == i) {
                    cout << j << " ";
                }
            }
            cout << endl;
        }
    }
};

JAVASCRIPT Implementation

// Heavy-Light Decomposition (HLD) in JavaScript (Path Maximum Query)

class SegmentTree {
  constructor(n) {
    this.n = n;
    this.tree = new Array(4 * n).fill(0);
  }

  build(arr, node = 1, l = 0, r = this.n - 1) {
    if (l === r) {
      this.tree[node] = arr[l];
      return;
    }
    const mid = Math.floor((l + r) / 2);
    this.build(arr, 2 * node, l, mid);
    this.build(arr, 2 * node + 1, mid + 1, r);
    this.tree[node] = Math.max(this.tree[2 * node], this.tree[2 * node + 1]);
  }

  query(L, R, node = 1, l = 0, r = this.n - 1) {
    if (r < L || l > R) return -Infinity;
    if (L <= l && r <= R) return this.tree[node];
    const mid = Math.floor((l + r) / 2);
    return Math.max(
      this.query(L, R, 2 * node, l, mid),
      this.query(L, R, 2 * node + 1, mid + 1, r)
    );
  }

  update(pos, val, node = 1, l = 0, r = this.n - 1) {
    if (l === r) {
      this.tree[node] = val;
      return;
    }
    const mid = Math.floor((l + r) / 2);
    if (pos <= mid) this.update(pos, val, 2 * node, l, mid);
    else this.update(pos, val, 2 * node + 1, mid + 1, r);
    this.tree[node] = Math.max(this.tree[2 * node], this.tree[2 * node + 1]);
  }
}

class HLD {
  constructor(n) {
    this.n = n;
    this.adj = Array.from({ length: n }, () => []);
    this.size = new Array(n).fill(0);
    this.depth = new Array(n).fill(0);
    this.parent = new Array(n).fill(-1);
    this.heavy = new Array(n).fill(-1);
    this.head = new Array(n).fill(0);
    this.pos = new Array(n).fill(0);
    this.time = 0;
    this.baseArray = new Array(n).fill(0);
    this.segTree = new SegmentTree(n);
  }

  addEdge(u, v, weight = 1) {
    this.adj[u].push([v, weight]);
    this.adj[v].push([u, weight]);
  }

  dfs(u, p) {
    this.size[u] = 1;
    let maxSize = 0;
    for (let [v, w] of this.adj[u]) {
      if (v === p) continue;
      this.parent[v] = u;
      this.depth[v] = this.depth[u] + 1;
      this.dfs(v, u);
      this.size[u] += this.size[v];
      if (this.size[v] > maxSize) {
        maxSize = this.size[v];
        this.heavy[u] = v;
      }
    }
  }

  decompose(u, h) {
    this.head[u] = h;
    this.pos[u] = this.time++;
    this.baseArray[this.pos[u]] = 0; // store edge weight if needed
    if (this.heavy[u] !== -1) this.decompose(this.heavy[u], h);
    for (let [v] of this.adj[u]) {
      if (v !== this.parent[u] && v !== this.heavy[u]) {
        this.decompose(v, v);
      }
    }
  }

  build(root = 0) {
    this.dfs(root, -1);
    this.decompose(root, root);
    this.segTree.build(this.baseArray);
  }

  queryPath(u, v) {
    let res = -Infinity;
    while (this.head[u] !== this.head[v]) {
      if (this.depth[this.head[u]] < this.depth[this.head[v]]) [u, v] = [v, u];
      const start = this.pos[this.head[u]];
      const end = this.pos[u];
      res = Math.max(res, this.segTree.query(start, end));
      u = this.parent[this.head[u]];
    }
    if (this.depth[u] > this.depth[v]) [u, v] = [v, u];
    res = Math.max(res, this.segTree.query(this.pos[u], this.pos[v]));
    return res;
  }

  updateNode(u, value) {
    this.segTree.update(this.pos[u], value);
  }
}

// Example usage:
const hld = new HLD(5);
hld.addEdge(0, 1);
hld.addEdge(1, 2);
hld.addEdge(1, 3);
hld.addEdge(3, 4);
hld.build();
hld.updateNode(2, 10);
hld.updateNode(4, 5);
console.log(hld.queryPath(2, 4)); // Output: 10