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