Heavy-Light Decomposition: Tree Path Queries

Key Insights

Heavy-Light Decomposition transforms tree path queries from O(n) to O(log² n) by partitioning edges into “heavy” chains that can be queried with segment trees
Any path from root to leaf crosses at most O(log n) light edges, which bounds the number of chain segments you need to process per query
HLD shines when you need both path queries and updates on static trees—for dynamic trees, consider Link-Cut Trees instead

The Problem with Naive Tree Queries

You have a tree with weighted nodes. You need to answer thousands of queries like “what’s the sum of values on the path from node A to node B?” or “update node X’s value to Y.” The naive approach walks the path for each query—O(n) per operation. With 10⁵ nodes and 10⁵ queries, you’re looking at 10¹⁰ operations. That’s not going to work.

Heavy-Light Decomposition (HLD) solves this by flattening tree paths into array segments that you can query with standard data structures. It’s a fundamental technique in competitive programming, but it also appears in graph databases, network analysis tools, and version control systems that model history as trees.

Core Concept: Heavy vs Light Edges

The decomposition hinges on a simple classification. For each internal node, its heavy child is the child with the largest subtree. All other children are light children. The edge to a heavy child is a heavy edge; edges to light children are light edges.

Here’s the critical insight: when you traverse from any node up to the root, you cross at most O(log n) light edges. Why? Each time you cross a light edge going upward, you at least double the subtree size (the light child’s subtree is at most half the parent’s subtree). You can only double O(log n) times before exceeding n.

Heavy edges form contiguous chains from some node down to a leaf. These chains become the backbone of our decomposition.

        1 (size=10)
       /|\
      2 3 4
    (6)(1)(2)
    /|    |
   5 6    7
  (3)(2) (1)
  /
 8
(2)
 |
 9
(1)

Heavy edges: 1→2, 2→5, 5→8, 8→9, 4→7
Light edges: 1→3, 1→4, 2→6

Chains: [1,2,5,8,9], [3], [6], [4,7]

Building the Decomposition

Construction requires two DFS passes. The first computes subtree sizes and identifies heavy children. The second assigns each node a position in a flattened array, ensuring nodes in the same chain occupy contiguous positions.

#include <vector>
using namespace std;

class HLD {
public:
    int n;
    vector<vector<int>> adj;
    vector<int> parent, depth, subtree_size;
    vector<int> chain_head, position, node_at_pos;
    vector<long long> values;
    int current_pos;

    HLD(int n) : n(n), adj(n), parent(n, -1), depth(n), 
                 subtree_size(n), chain_head(n), position(n), 
                 node_at_pos(n), values(n), current_pos(0) {}

    void add_edge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void dfs_size(int u, int p, int d) {
        parent[u] = p;
        depth[u] = d;
        subtree_size[u] = 1;
        
        // Remove parent from adjacency list, put heavy child first
        auto it = find(adj[u].begin(), adj[u].end(), p);
        if (it != adj[u].end()) adj[u].erase(it);
        
        int heavy_idx = -1, max_size = 0;
        for (int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i];
            dfs_size(v, u, d + 1);
            subtree_size[u] += subtree_size[v];
            if (subtree_size[v] > max_size) {
                max_size = subtree_size[v];
                heavy_idx = i;
            }
        }
        // Move heavy child to front
        if (heavy_idx > 0) swap(adj[u][0], adj[u][heavy_idx]);
    }

    void dfs_decompose(int u, int head) {
        chain_head[u] = head;
        position[u] = current_pos;
        node_at_pos[current_pos] = u;
        current_pos++;

        if (adj[u].empty()) return;
        
        // Heavy child continues the chain
        dfs_decompose(adj[u][0], head);
        
        // Light children start new chains
        for (int i = 1; i < adj[u].size(); i++) {
            dfs_decompose(adj[u][i], adj[u][i]);
        }
    }

    void build(int root = 0) {
        dfs_size(root, -1, 0);
        dfs_decompose(root, root);
    }
};

The key trick in dfs_size: we reorder children so the heavy child comes first. This makes dfs_decompose simpler—the first child always continues the current chain, and remaining children start new chains.

Answering Path Queries

To query the path from u to v, we repeatedly “climb” from the deeper node toward their lowest common ancestor (LCA). At each step, we query the segment from the current node to its chain head, then jump to the parent of the chain head.

// Add to HLD class
long long query_path(int u, int v) {
    long long result = 0;
    
    while (chain_head[u] != chain_head[v]) {
        // Work with the node whose chain head is deeper
        if (depth[chain_head[u]] < depth[chain_head[v]]) {
            swap(u, v);
        }
        // Query from u up to its chain head
        result += query_segment(position[chain_head[u]], position[u]);
        // Jump to parent of chain head
        u = parent[chain_head[u]];
    }
    
    // u and v are now in the same chain
    if (depth[u] > depth[v]) swap(u, v);
    result += query_segment(position[u], position[v]);
    
    return result;
}

The loop terminates when both nodes share the same chain head—meaning they’re on the same chain and we can query the final segment directly.

Integration with Segment Trees

The position array maps tree nodes to array indices. We build a segment tree over this flattened array to get O(log n) per segment query. Combined with O(log n) segments per path, we achieve O(log² n) per path query.

class SegmentTree {
    vector<long long> tree;
    int n;
    
public:
    SegmentTree(int n) : n(n), tree(4 * n, 0) {}
    
    void update(int node, int start, int end, int idx, long long 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] = tree[2*node] + tree[2*node+1];
    }
    
    long long query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return 0;
        if (l <= start && end <= r) return tree[node];
        int mid = (start + end) / 2;
        return query(2*node, start, mid, l, r) + 
               query(2*node+1, mid+1, end, l, r);
    }
    
    void update(int idx, long long val) { update(1, 0, n-1, idx, val); }
    long long query(int l, int r) { return query(1, 0, n-1, l, r); }
};

Integrate it into the HLD class:

class HLDWithSegTree : public HLD {
    SegmentTree seg;
    
public:
    HLDWithSegTree(int n) : HLD(n), seg(n) {}
    
    void set_value(int u, long long val) {
        values[u] = val;
        seg.update(position[u], val);
    }
    
    long long query_segment(int l, int r) {
        return seg.query(l, r);
    }
    
    long long path_sum(int u, int v) {
        return query_path(u, v);  // Uses query_segment internally
    }
};

Complexity Analysis & Optimizations

Time complexity: O(n) preprocessing, O(log² n) per query or update. The log² comes from O(log n) chain segments, each requiring O(log n) segment tree operations.

Space complexity: O(n) for all arrays plus O(n) for the segment tree.

Optimizations worth knowing:

Euler tour for subtree queries: If you also need subtree queries (sum of all values in node u’s subtree), the position array already handles this—nodes in a subtree occupy contiguous positions from position[u] to position[u] + subtree_size[u] - 1.
Lazy propagation: For range updates on paths (add X to all nodes from u to v), combine HLD with a lazy segment tree. Same complexity, much more powerful.
Reducing to O(log n): Use a global segment tree with fractional cascading or tree decomposition tricks. Rarely worth the complexity in practice.

Practical Applications & Alternatives

Where HLD appears in production:

Version control: Git’s commit history is a DAG, but branch histories are trees. Finding common ancestors and computing diffs along paths uses similar decomposition ideas.
Network routing: Computing path metrics (latency, bandwidth bottleneck) in tree-structured networks.
Databases: Tree-indexed data structures that need range queries along hierarchical paths.

When to use alternatives:

Binary lifting: Simpler to implement if you only need LCA queries without path aggregation. O(log n) per query, O(n log n) space.
Link-Cut Trees: When the tree structure changes dynamically (adding/removing edges). Same O(log n) query time but with O(log n) amortized updates. More complex to implement correctly.
Centroid decomposition: Better for some distance-based queries. Different trade-offs.

Complete Working Example

Here’s a full solution for the classic “path maximum query with point updates” problem:

#include <bits/stdc++.h>
using namespace std;

class HLDMax {
    int n, pos_counter = 0;
    vector<vector<int>> adj;
    vector<int> parent, depth, sz, chain_head, pos;
    vector<long long> seg;
    
    void dfs1(int u, int p, int d) {
        parent[u] = p; depth[u] = d; sz[u] = 1;
        adj[u].erase(remove(adj[u].begin(), adj[u].end(), p), adj[u].end());
        for (int& v : adj[u]) {
            dfs1(v, u, d + 1);
            sz[u] += sz[v];
            if (sz[v] > sz[adj[u][0]]) swap(v, adj[u][0]);
        }
    }
    
    void dfs2(int u, int h) {
        chain_head[u] = h; pos[u] = pos_counter++;
        for (int v : adj[u]) dfs2(v, v == adj[u][0] ? h : v);
    }
    
    void seg_update(int i, long long v) {
        for (seg[i += n] = v; i > 1; i >>= 1)
            seg[i >> 1] = max(seg[i], seg[i ^ 1]);
    }
    
    long long seg_query(int l, int r) {
        long long res = LLONG_MIN;
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = max(res, seg[l++]);
            if (r & 1) res = max(res, seg[--r]);
        }
        return res;
    }
    
public:
    HLDMax(int n) : n(n), adj(n), parent(n), depth(n), sz(n),
                    chain_head(n), pos(n), seg(2 * n, LLONG_MIN) {}
    
    void add_edge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    void build(int root = 0) { dfs1(root, -1, 0); dfs2(root, root); }
    
    void update(int u, long long v) { seg_update(pos[u], v); }
    
    long long query(int u, int v) {
        long long res = LLONG_MIN;
        while (chain_head[u] != chain_head[v]) {
            if (depth[chain_head[u]] < depth[chain_head[v]]) swap(u, v);
            res = max(res, seg_query(pos[chain_head[u]], pos[u]));
            u = parent[chain_head[u]];
        }
        if (depth[u] > depth[v]) swap(u, v);
        return max(res, seg_query(pos[u], pos[v]));
    }
};

int main() {
    HLDMax hld(5);
    hld.add_edge(0, 1);
    hld.add_edge(0, 2);
    hld.add_edge(1, 3);
    hld.add_edge(1, 4);
    hld.build();
    
    hld.update(0, 5);
    hld.update(1, 3);
    hld.update(3, 7);
    hld.update(4, 2);
    
    cout << hld.query(3, 4) << endl;  // max on path 3→1→4 = 7
    cout << hld.query(2, 3) << endl;  // max on path 2→0→1→3 = 7
    
    return 0;
}

HLD is one of those techniques that looks intimidating until you implement it once. The core idea—partition into chains, flatten to array, use your favorite 1D data structure—is elegant and widely applicable. Master it, and you’ll have a powerful tool for any tree path problem.