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
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
PYTHON Implementation
# Heavy-Light Decomposition (HLD) in Python for path maximum queries
class SegmentTree:
def __init__(self, n):
self.n = n
self.tree = [0] * (4 * n)
def build(self, arr, node=1, l=0, r=None):
if r is None:
r = self.n - 1
if l == r:
self.tree[node] = arr[l]
return
mid = (l + r) // 2
self.build(arr, node*2, l, mid)
self.build(arr, node*2+1, mid+1, r)
self.tree[node] = max(self.tree[node*2], self.tree[node*2+1])
def query(self, L, R, node=1, l=0, r=None):
if r is None:
r = self.n - 1
if r < L or l > R:
return float('-inf')
if L <= l and r <= R:
return self.tree[node]
mid = (l + r) // 2
return max(
self.query(L, R, node*2, l, mid),
self.query(L, R, node*2+1, mid+1, r)
)
def update(self, pos, val, node=1, l=0, r=None):
if r is None:
r = self.n - 1
if l == r:
self.tree[node] = val
return
mid = (l + r) // 2
if pos <= mid:
self.update(pos, val, node*2, l, mid)
else:
self.update(pos, val, node*2+1, mid+1, r)
self.tree[node] = max(self.tree[node*2], self.tree[node*2+1])
class HLD:
def __init__(self, n):
self.n = n
self.adj = [[] for _ in range(n)]
self.size = [0]*n
self.depth = [0]*n
self.parent = [-1]*n
self.heavy = [-1]*n
self.head = [0]*n
self.pos = [0]*n
self.time = 0
self.baseArray = [0]*n
self.segTree = SegmentTree(n)
def add_edge(self, u, v):
self.adj[u].append(v)
self.adj[v].append(u)
def dfs(self, u, p):
self.size[u] = 1
max_size = 0
for v in self.adj[u]:
if v == p:
continue
self.parent[v] = u
self.depth[v] = self.depth[u] + 1
self.dfs(v, u)
self.size[u] += self.size[v]
if self.size[v] > max_size:
max_size = self.size[v]
self.heavy[u] = v
def decompose(self, u, h):
self.head[u] = h
self.pos[u] = self.time
self.time += 1
if self.heavy[u] != -1:
self.decompose(self.heavy[u], h)
for v in self.adj[u]:
if v != self.parent[u] and v != self.heavy[u]:
self.decompose(v, v)
def build(self, root=0):
self.dfs(root, -1)
self.decompose(root, root)
self.segTree.build(self.baseArray)
def query_path(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.segTree.query(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
res = max(res, self.segTree.query(self.pos[u], self.pos[v]))
return res
def update_node(self, u, val):
self.segTree.update(self.pos[u], val)
# Example usage
hld = HLD(5)
hld.add_edge(0, 1)
hld.add_edge(1, 2)
hld.add_edge(1, 3)
hld.add_edge(3, 4)
hld.build()
hld.update_node(2, 10)
hld.update_node(4, 5)
print(hld.query_path(2, 4)) # Output: 10