Algorithm Deep Dive: Heavy-Light Decomposition (HLD)

A Bit of History

Heavy-Light Decomposition (HLD) was introduced by Daniel Sleator and Robert Tarjan in 1983 in their landmark paper on dynamic trees and link-cut trees. Their goal was to maintain forest structures under link and cut operations while answering path queries efficiently. The heavy-light path partitioning idea was later recognized as a standalone data structuring technique for static trees: by linearizing heavy paths in DFS order, a standard 1D Segment Tree or Fenwick Tree can execute path queries (e.g., path max, path sum, path update) on an arbitrary tree in $O(\log^2 N)$ time.

Heavy vs. Light Edges

In a rooted tree with $N$ vertices, let $\text{subtree\_size}(u)$ be the number of nodes in the subtree rooted at $u$:

Heavy Edge: An edge $(u, v)$ from parent $u$ to child $v$ is heavy if $\text{subtree\_size}(v) > \frac{1}{2} \cdot \text{subtree\_size}(u)$. Each node $u$ can have at most one heavy child.
Light Edge: All other edges connecting $u$ to its children are light.

Connected heavy edges form contiguous heavy paths (chains). Light edges serve as bridges jumping from one heavy path to the top of another.

Working Principle & Construction

Constructing HLD requires two DFS passes:

First DFS (Subtree Sizes & Heavy Children): Compute node depths, parent pointers, subtree sizes, and identify the heavy child for each node (the child with the maximum subtree size).
Second DFS (Path Linearization & Head Assignment): Traverse the tree prioritizing heavy children first. Assign a 1D position (pos[u]) to each node. Because heavy children are visited consecutively, nodes on the same heavy path receive contiguous 1D indices! Also assign head[u], the top node of the heavy path containing $u$.

Key Insight

Because nodes along a heavy path have contiguous 1D position indices in the second DFS traversal, an entire segment of a heavy path corresponds to a contiguous subsegment [pos[top], pos[u]] in a 1D Segment Tree!

Path Queries & Updates

To query or update the path between two nodes $u$ and $v$:

While $u$ and $v$ are on different heavy paths (i.e., head[u] != head[v]):
- Pick the node whose head is deeper (say $u$).
- Query/update the contiguous 1D range [pos[head[u]], pos[u]] in the Segment Tree.
- Jump $u$ up to the parent of its chain's head: u = parent[head[u]] (crossing a light edge).
Once both nodes share the same heavy path (head[u] == head[v]), query/update the remaining range between them: [min(pos[u], pos[v]), max(pos[u], pos[v])].

Worked Example

Consider a tree rooted at 0 with 10 nodes. Suppose path from 0 to 8 consists of 2 heavy paths connected by 1 light edge:

Querying path $0 \to 8$: Node 8 is on a heavy path starting at head 5. We query range [pos[5], pos[8]] in $O(\log N)$ via Segment Tree.
Then jump node 8 up across the light edge: 8 -> parent[5] = 2.
Node 2 and Node 0 share the same heavy path (head 0). Query remaining range [pos[0], pos[2]] in $O(\log N)$.
Total path query time: $2 \times O(\log N) = O(\log^2 N)$.

Why Any Path Has O(log N) Light Edges

Crucially, traversing a light edge $(u, v)$ means moving from parent $u$ to child $v$ where $\text{subtree\_size}(v) \le \frac{1}{2} \cdot \text{subtree\_size}(u)$. Therefore, moving down a light edge cuts the subtree size at least in half!

Starting from the root with $N$ nodes, you can traverse at most $\lfloor \log_2 N \rfloor$ light edges before reaching a leaf. Consequently, **any simple path in the tree crosses at most $O(\log N)$ light edges**, jumping between at most $O(\log N)$ distinct heavy paths.

Complexity Analysis

Operation	Time Complexity	Space Complexity
Decomposition Construction (2 DFS passes)	$O(N)$	$O(N)$
Segment Tree Construction	$O(N)$	$O(N)$
Path Query / Path Update	$O(\log^2 N)$	$O(1)$ auxiliary
Subtree Query / Subtree Update	$O(\log N)$	$O(1)$ auxiliary

Implementation

class SegmentTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (4 * size)

    def update(self, node, start, end, idx, val):
        if start == end:
            self.tree[node] = val
            return
        mid = (start + end) // 2
        if start <= idx <= mid:
            self.update(2 * node, start, mid, idx, val)
        else:
            self.update(2 * node + 1, mid + 1, end, idx, val)
        self.tree[node] = max(self.tree[2 * node], self.tree[2 * node + 1])

    def query(self, node, start, end, l, r):
        if r < start or end < l:
            return -float('inf')
        if l <= start and end <= r:
            return self.tree[node]
        mid = (start + end) // 2
        p1 = self.query(2 * node, start, mid, l, r)
        p2 = self.query(2 * node + 1, mid + 1, end, l, r)
        return max(p1, p2)

class HeavyLightDecomposition:
    def __init__(self, n, adj, values, root=0):
        self.n = n
        self.adj = adj
        self.values = values
        self.parent = [0] * n
        self.depth = [0] * n
        self.heavy = [-1] * n
        self.head = [0] * n
        self.pos = [0] * n
        self.cur_pos = 0
        
        self.seg = SegmentTree(n)
        self._dfs1(root, -1, 0)
        self._dfs2(root, root)

    def _dfs1(self, u, p, d):
        self.parent[u] = p
        self.depth[u] = d
        size = 1
        max_c_size = 0
        for v in self.adj[u]:
            if v != p:
                c_size = self._dfs1(v, u, d + 1)
                size += c_size
                if c_size > max_c_size:
                    max_c_size = c_size
                    self.heavy[u] = v
        return size

    def _dfs2(self, u, h):
        self.head[u] = h
        self.pos[u] = self.cur_pos
        self.seg.update(1, 0, self.n - 1, self.cur_pos, self.values[u])
        self.cur_pos += 1

        if self.heavy[u] != -1:
            self._dfs2(self.heavy[u], h)
        for v in self.adj[u]:
            if v != self.parent[u] and v != self.heavy[u]:
                self._dfs2(v, v)

    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.seg.query(1, 0, self.n - 1, 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.seg.query(1, 0, self.n - 1, self.pos[u], self.pos[v]))
        return res

# Example Usage
n = 6
values = [10, 20, 30, 40, 50, 60]
adj = [[] for _ in range(n)]
edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)

hld = HeavyLightDecomposition(n, adj, values, root=0)
print("Max value on path (3, 5):", hld.query_path(3, 5)) # Output: 60

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class SegmentTree {
    int n;
    vector<int> tree;
public:
    SegmentTree(int size) : n(size) {
        tree.assign(4 * size, 0);
    }

    void update(int node, int start, int end, int idx, int val) {
        if (start == end) {
            tree[node] = val;
            return;
        }
        int mid = (start + end) / 2;
        if (idx <= mid) update(2 * node, start, mid, idx, val);
        else update(2 * node + 1, mid + 1, end, idx, val);
        tree[node] = max(tree[2 * node], tree[2 * node + 1]);
    }

    int query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return -1e9;
        if (l <= start && end <= r) return tree[node];
        int mid = (start + end) / 2;
        return max(query(2 * node, start, mid, l, r),
                   query(2 * node + 1, mid + 1, end, l, r));
    }
};

class HLD {
    int n, cur_pos;
    vector<vector<int>> adj;
    vector<int> parent, depth, heavy, head, pos, values;
    SegmentTree seg;

    int dfs1(int u, int p, int d) {
        parent[u] = p; depth[u] = d;
        int size = 1, max_c_size = 0;
        for (int v : adj[u]) {
            if (v != p) {
                int c_size = dfs1(v, u, d + 1);
                size += c_size;
                if (c_size > max_c_size) {
                    max_c_size = c_size;
                    heavy[u] = v;
                }
            }
        }
        return size;
    }

    void dfs2(int u, int h) {
        head[u] = h; pos[u] = cur_pos;
        seg.update(1, 0, n - 1, cur_pos, values[u]);
        cur_pos++;

        if (heavy[u] != -1) dfs2(heavy[u], h);
        for (int v : adj[u]) {
            if (v != parent[u] && v != heavy[u]) {
                dfs2(v, v);
            }
        }
    }

public:
    HLD(int n, const vector<vector<int>>& adj, const vector<int>& values, int root = 0)
        : n(n), adj(adj), values(values), cur_pos(0), seg(n) {
        parent.resize(n); depth.resize(n);
        heavy.assign(n, -1); head.resize(n); pos.resize(n);
        dfs1(root, -1, 0);
        dfs2(root, root);
    }

    int queryPath(int u, int v) {
        int res = -1e9;
        while (head[u] != head[v]) {
            if (depth[head[u]] < depth[head[v]]) swap(u, v);
            res = max(res, seg.query(1, 0, n - 1, pos[head[u]], pos[u]));
            u = parent[head[u]];
        }
        if (depth[u] > depth[v]) swap(u, v);
        res = max(res, seg.query(1, 0, n - 1, pos[u], pos[v]));
        return res;
    }
};

int main() {
    int n = 6;
    vector<int> values = {10, 20, 30, 40, 50, 60};
    vector<vector<int>> adj(n);
    vector<pair<int, int>> edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}};
    for (auto p : edges) {
        adj[p.first].push_back(p.second);
        adj[p.second].push_back(p.first);
    }

    HLD hld(n, adj, values, 0);
    cout << "Max value on path (3, 5): " << hld.queryPath(3, 5) << endl; // 60
    return 0;
}

import java.util.*;

public class HLD {
    static class SegmentTree {
        int n;
        int[] tree;
        public SegmentTree(int size) {
            this.n = size;
            this.tree = new int[4 * size];
        }
        public void update(int node, int start, int end, int idx, int val) {
            if (start == end) { tree[node] = val; return; }
            int mid = (start + end) / 2;
            if (idx <= mid) update(2 * node, start, mid, idx, val);
            else update(2 * node + 1, mid + 1, end, idx, val);
            tree[node] = Math.max(tree[2 * node], tree[2 * node + 1]);
        }
        public int query(int node, int start, int end, int l, int r) {
            if (r < start || end < l) return (int)-1e9;
            if (l <= start && end <= r) return tree[node];
            int mid = (start + end) / 2;
            return Math.max(query(2 * node, start, mid, l, r),
                            query(2 * node + 1, mid + 1, end, l, r));
        }
    }

    private int n, curPos;
    private List<List<Integer>> adj;
    private int[] parent, depth, heavy, head, pos, values;
    private SegmentTree seg;

    public HLD(int n, List<List<Integer>> adj, int[] values, int root) {
        this.n = n; this.adj = adj; this.values = values;
        this.curPos = 0; this.seg = new SegmentTree(n);
        this.parent = new int[n]; this.depth = new int[n];
        this.heavy = new int[n]; Arrays.fill(heavy, -1);
        this.head = new int[n]; this.pos = new int[n];

        dfs1(root, -1, 0);
        dfs2(root, root);
    }

    private int dfs1(int u, int p, int d) {
        parent[u] = p; depth[u] = d;
        int size = 1, maxCSize = 0;
        for (int v : adj.get(u)) {
            if (v != p) {
                int cSize = dfs1(v, u, d + 1);
                size += cSize;
                if (cSize > maxCSize) {
                    maxCSize = cSize;
                    heavy[u] = v;
                }
            }
        }
        return size;
    }

    private void dfs2(int u, int h) {
        head[u] = h; pos[u] = curPos;
        seg.update(1, 0, n - 1, curPos, values[u]);
        curPos++;

        if (heavy[u] != -1) dfs2(heavy[u], h);
        for (int v : adj.get(u)) {
            if (v != parent[u] && v != heavy[u]) {
                dfs2(v, v);
            }
        }
    }

    public int queryPath(int u, int v) {
        int res = (int)-1e9;
        while (head[u] != head[v]) {
            if (depth[head[u]] < depth[head[v]]) {
                int temp = u; u = v; v = temp;
            }
            res = Math.max(res, seg.query(1, 0, n - 1, pos[head[u]], pos[u]));
            u = parent[head[u]];
        }
        if (depth[u] > depth[v]) {
            int temp = u; u = v; v = temp;
        }
        res = Math.max(res, seg.query(1, 0, n - 1, pos[u], pos[v]));
        return res;
    }

    public static void main(String[] args) {
        int n = 6;
        int[] values = {10, 20, 30, 40, 50, 60};
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());

        int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}};
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }

        HLD hld = new HLD(n, adj, values, 0);
        System.out.println("Max value on path (3, 5): " + hld.queryPath(3, 5)); // 60
    }
}

Real-World Applications

Case Study

Network Backbones & Dynamic Tree Querying

In telecommunication backbone networks and distributed routing trees, capacity or bottleneck metrics along network paths need real-time updates and queries. HLD allows network monitoring systems to update link capacities and query path bottlenecks in $O(\log^2 N)$ time.

Network RoutingTree Data Structures

Exercises

Show how HLD can be modified to support Subtree Queries (e.g., sum of all nodes in $u$'s subtree) in $O(\log N)$ time.
Extend the HLD implementation to support edge weights instead of vertex weights.
Compare HLD with Centroid Decomposition for path queries and range updates.
Challenge: Implement HLD with Lazy Propagation on the Segment Tree to support path range updates in $O(\log^2 N)$ time.

Limitations

Static Tree Constraint & Constant Factor

Standard HLD works only on static trees (fixed structure). If edges are dynamically inserted/deleted, Link-Cut Trees (Sleator & Tarjan) must be used instead. Additionally, HLD carries a notable constant factor due to 2 DFS passes and multiple Segment Tree range queries per path.

Operation	Time Complexity	Space Complexity
Decomposition Construction (2 DFS passes)	\(O(N)\)	\(O(N)\)
Segment Tree Construction	\(O(N)\)	\(O(N)\)
Path Query / Path Update	\(O(\log^2 N)\)	\(O(1)\) auxiliary
Subtree Query / Subtree Update	\(O(\log N)\)	\(O(1)\) auxiliary

Cookie Consent

Heavy-Light Decomposition (HLD)

Contents

A Bit of History

Heavy vs. Light Edges

Working Principle & Construction

Key Insight

Path Queries & Updates

Worked Example

Why Any Path Has O(log N) Light Edges

Complexity Analysis

Implementation

Real-World Applications

Network Backbones & Dynamic Tree Querying

Exercises

Limitations

Static Tree Constraint & Constant Factor

Cookie Consent

Heavy-Light Decomposition (HLD)

Contents

A Bit of History

Heavy vs. Light Edges

Working Principle & Construction

Key Insight

Path Queries & Updates

Worked Example

Why Any Path Has O(log N) Light Edges

Complexity Analysis

Implementation

Real-World Applications

Network Backbones & Dynamic Tree Querying

Exercises

Limitations

Static Tree Constraint & Constant Factor

Related Deep Dives

Graph Theory Series

Lowest Common Ancestor (LCA)

Part 11: Trees & Minimum Spanning Trees