Chapter 104

Home

Heavy Light Decomposition

HLD decomposes a tree into disjoint paths so any root-to-leaf path touches O(log N) paths. Combined with a segment tree, you can query/update any path (u→v) in O(log² N). Essential for path queries on trees.

HLD Core Idea

C++ — HLD path query skeleton

struct HLD {
    vector> adj;
    vector parent, depth, heavy, head, pos;
    int cur_pos;
    SegTree seg;  // segment tree on the base array

    int dfs(int u) {
        int sz = 1, max_sz = 0;
        for (int v : adj[u]) if (v != parent[u]) {
            parent[v] = u;
            depth[v] = depth[u] + 1;
            int sub = dfs(v);
            if (sub > max_sz) { max_sz = sub; heavy[u] = v; }
            sz += sub;
        }
        return sz;
    }

    void decompose(int u, int h) {
        head[u] = h; pos[u] = cur_pos++;
        if (heavy[u] != -1) decompose(heavy[u], h);
        for (int v : adj[u])
            if (v != parent[u] && v != heavy[u]) decompose(v, v);
    }

    int path_query(int u, int v) {
        int ans = 0;
        while (head[u] != head[v]) {
            if (depth[head[u]] < depth[head[v]]) swap(u, v);
            ans += seg.query(pos[head[u]], pos[u]);
            u = parent[head[u]];
        }
        if (depth[u] > depth[v]) swap(u, v);
        ans += seg.query(pos[u], pos[v]);
        return ans;
    }
};

// O(log² N) per path query/update.

💡 When to use HLD

Any problem involving "query/update values on the path between two nodes in a tree." Without HLD, you'd need LCA + brute-force walking, which is O(N) per query. HLD makes it O(log² N).

Key Takeaways