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

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