Heavy-Light Decomposition Tutorial

If you have ever worked on algorithmic problems involving paths or subtrees, you have likely encountered the challenge of querying and updating values along tree paths without hitting Time Limit Exceeded (TLE) limits. While query operations on an array are simple using segment trees, trees add a layer of complexity. If you try to brute-force a path query using depth-first search (DFS) for every query, the system will fall apart quickly when the number of nodes n reaches 1e5.

This is where Heavy-Light Decomposition (HLD) comes in. It is an advanced technique that breaks down a tree into linear paths, allowing you to use a segment tree or Binary Indexed Tree (BIT) to perform updates and queries on any tree path in logarithmic time.

Imagine you are given a tree of n nodes and need to support queries like finding the maximum value or the sum of values along the path between node u and node v, alongside point updates on node values. If the tree is a straight line, it acts as a simple array, and a segment tree can handle queries in O(log n) time. However, trees branch out in complex ways.

HLD solves this by decomposing the tree into a set of disjoint paths (chains). The nodes along each chain are mapped to contiguous segments in an array, allowing you to query paths using a segment tree.

The logic behind HLD is elegant:

First, we run a DFS to compute the size of the subtree rooted at each node.

Second, for each node, we identify the child with the largest subtree. The edge connecting the parent to this child is classified as a 'heavy' edge, while the edges to the other children are classified as 'light' edges.

Third, we decompose the tree into chains. A heavy chain is formed by following heavy edges down the tree. When we follow a light edge, we start a new heavy chain.

Because the size of the subtree halves every time we traverse a light edge, any path from a node to the root of the tree intersects at most O(log n) different heavy chains. This means we can query or update values along any path by splitting it into at most O(log n) segment tree queries.

Let's look at a standard implementation in C++.

void dfs(int u, int p) {
    parent[u] = p;
    size[u] = 1;
    int max_sz = 0;
    for (int v : adj[u]) {
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        dfs(v, u);
        size[u] += size[v];
        if (size[v] > max_sz) {
            max_sz = size[v];
            heavy[u] = v;
        }
    }
}

// Step 2: Decompose the tree into heavy chains
void decompose(int u, int h) {
    head[u] = h;
    pos[u] = cur_pos++;
    if (heavy[u]) decompose(heavy[u], h);
    for (int v : adj[u]) {
        if (v != parent[u] && v != heavy[u]) {
            decompose(v, v);
        }
    }
}

// Step 3: Query maximum value along the path between u and v
int query(int u, int v) {
    int res = 0;
    while (head[u] != head[v]) {
        if (depth[head[u]] < depth[head[v]]) swap(u, v);
        res = max(res, segtree.query(pos[head[u]], pos[u]));
        u = parent[head[u]];
    }
    if (depth[u] > depth[v]) swap(u, v);
    res = max(res, segtree.query(pos[u], pos[v]));
    return res; 
}

You should consider using HLD when your problem requires path queries between arbitrary nodes on a tree, especially if node values are updated dynamically. If you only need to query static paths without updates, a binary lifting approach for Lowest Common Ancestor (LCA) or a simple prefix sum might suffice. For subtree queries without path queries, a simpler Euler Tour technique is usually easier to implement.

To solidify your understanding of HLD, try implementing it on these Codeforces problems:

• CF 343D (Water Tree): Excellent practice for combining path queries with subtree updates.

• CF 609E (Minimum Spanning Tree for Each Edge): A classic application using HLD to find the maximum edge on a path.

• CF 342E (Xenia and Tree): A hybrid problem that can be solved with centroid decomposition or HLD.

Learning Heavy-Light Decomposition takes time and patience. The first time I implemented it, my code was a confusing mix of DFS passes, tracking positions, and debugging segment trees. But once the logic clicks, it becomes an incredibly clean and satisfying tool to build.