AntInLoop

Heavy-Light Decomposition (HLD)

Heavy-Light Decomposition splits a rooted tree into disjoint heavy chains so any path between two nodes crosses at most O(log n) chains, reducing tree path queries and updates to Segment Tree operations in O(log^2 n).

Difficulty: Hard · Interactive Visualizer · C++ / Python / Java / JS Code

Heavy-Light Decomposition (HLD)

Heavy-Light Decomposition (HLD) decomposes any rooted tree of $n$ vertices into vertex-disjoint heavy paths (chains) such that any path from a node to the root crosses at most $\lfloor \log_2 n \rfloor$ light edges. By laying out each heavy chain contiguously in a single flat array (Euler order visiting the heavy child first!), any tree path query or update splits into at most $O(\log n)$ contiguous intervals—handled by a Segment Tree in $O(\log^2 n)$ time (and $O(\log n)$ for subtree queries and LCA)!

At a Glance

| Operation | Time Complexity |

| :--- | :--- |

| Build (2 DFS + Segment Tree) | $O(n)$ |

| Point Update on Node | $O(\log n)$ |

| Path Query / Path Update (u to v) | $O(\log^2 n)$ |

| Subtree Query / Update | $O(\log n)$ (contiguous [pos[u], pos[u] + sz[u] - 1]) |

| LCA Query | $O(\log n)$ |

| Auxiliary Space | $O(n)$ |

---

How It Works

1. DFS 1 (Subtree Sizes & Heavy Child): For each node u, compute parent[u], depth[u], sz[u], and pick heavy[u] = the child v with the largest sz[v].

2. DFS 2 (Chain Decomposition): Assign each node its chain top head[u] and contiguous array index pos[u] = timer++. Always recurse into heavy[u] first (keeping head[heavy[u]] = head[u]), then recurse into every light child v with head[v] = v.

3. Path Query (u, v): While head[u] != head[v]:

  • Ensure depth[head[u]] >= depth[head[v]] (swap u, v if not).
  • Query Segment Tree on [pos[head[u]], pos[u]], then jump u = parent[head[u]].
  • Finally, u and v are on the same chain: ensure depth[u] <= depth[v] and query [pos[u], pos[v]]!

---

Complexity & Key Insights

  • Why At Most $\log_2 n$ Light Edges: Every time you step down a light edge (u → v), sz[v] <= sz[u] / 2 (otherwise v would have been the heavy child!). The subtree size halves at every light edge, so any root-to-leaf path has at most $\lfloor \log_2 n \rfloor$ light edges.
  • Edge-Weighted Trees: Store each edge's weight on its deeper endpoint (child node). When querying path (u, v), exclude the LCA itself by querying [pos[u] + 1, pos[v]] in the final same-chain step!

---

Practice Problems

Easy

1. Lowest Common Ancestor (LCA) via HLD in $O(\log n)$

Compute the LCA of any two nodes u, v in $O(\log n)$ time and $O(n)$ memory (no $O(n \log n)$ binary-lifting table!).

Approach: Jump the deeper chain head (u = parent[head[u]]) until head[u] == head[v], then return whichever of u, v has smaller depth. Time: $O(\log n)$. Space: $O(n)$.

<details>

<summary>Show C++ Solution</summary>

#include <iostream>
#include <utility>
#include <vector>

struct HLD {
    int n, timer = 0;
    std::vector<std::vector<int>> adj;
    std::vector<int> parent, depth, heavy, head, pos, sz;

    explicit HLD(int n) : n(n), adj(n), parent(n, -1), depth(n, 0),
                          heavy(n, -1), head(n, 0), pos(n, 0), sz(n, 0) {}

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

    int dfs1(int u, int p) {
        parent[u] = p;
        sz[u] = 1;
        int maxChild = 0;
        for (int v : adj[u]) {
            if (v == p) continue;
            depth[v] = depth[u] + 1;
            int sub = dfs1(v, u);
            sz[u] += sub;
            if (sub > maxChild) { maxChild = sub; heavy[u] = v; }
        }
        return sz[u];
    }

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

    void build(int root = 0) { dfs1(root, -1); dfs2(root, root); }

    int lca(int u, int v) const {
        while (head[u] != head[v]) {
            if (depth[head[u]] < depth[head[v]]) std::swap(u, v);
            u = parent[head[u]];
        }
        return depth[u] < depth[v] ? u : v;
    }
};

int main() {
    HLD hld(7);
    hld.addEdge(0, 1); hld.addEdge(0, 2); hld.addEdge(1, 3);
    hld.addEdge(1, 4); hld.addEdge(2, 5); hld.addEdge(4, 6);
    hld.build(0);
    std::cout << hld.lca(3, 6) << " " << hld.lca(5, 6) << "\n"; // 1 0
    return 0;
}

</details>

2. Dynamic Path Maximum Queries + Point Updates (CSES Path Queries II)

Support updating a node's value and querying the maximum node value along the path between u and v.

Approach: Pair HLD with an iterative Segment Tree over pos[0..n-1]. Time: $O(\log n)$ update, $O(\log^2 n)$ path max query.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <climits>
#include <iostream>
#include <utility>
#include <vector>

struct MaxSegTree {
    int n;
    std::vector<int> seg;
    explicit MaxSegTree(int n) : n(n), seg(2 * n, INT_MIN) {}
    void update(int idx, int val) {
        for (seg[idx += n] = val; idx > 1; idx >>= 1)
            seg[idx >> 1] = std::max(seg[idx], seg[idx ^ 1]);
    }
    int query(int l, int r) const { // inclusive [l, r]
        int res = INT_MIN;
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = std::max(res, seg[l++]);
            if (r & 1) res = std::max(res, seg[--r]);
        }
        return res;
    }
};

struct HLDMax {
    int n, timer = 0;
    std::vector<std::vector<int>> adj;
    std::vector<int> parent, depth, heavy, head, pos;
    MaxSegTree st;

    explicit HLDMax(int n) : n(n), adj(n), parent(n, -1), depth(n, 0),
                             heavy(n, -1), head(n, 0), pos(n, 0), st(n) {}
    void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); }

    int dfs1(int u, int p) {
        parent[u] = p;
        int sz = 1, best = 0;
        for (int v : adj[u]) {
            if (v == p) continue;
            depth[v] = depth[u] + 1;
            int sub = dfs1(v, u);
            sz += sub;
            if (sub > best) { best = sub; heavy[u] = v; }
        }
        return sz;
    }
    void dfs2(int u, int h) {
        head[u] = h; pos[u] = timer++;
        if (heavy[u] != -1) dfs2(heavy[u], h);
        for (int v : adj[u]) if (v != parent[u] && v != heavy[u]) dfs2(v, v);
    }
    void build(const std::vector<int>& vals) {
        dfs1(0, -1); dfs2(0, 0);
        for (int i = 0; i < n; ++i) st.update(pos[i], vals[i]);
    }
    void setVal(int u, int val) { st.update(pos[u], val); }
    int queryPath(int u, int v) const {
        int ans = INT_MIN;
        while (head[u] != head[v]) {
            if (depth[head[u]] < depth[head[v]]) std::swap(u, v);
            ans = std::max(ans, st.query(pos[head[u]], pos[u]));
            u = parent[head[u]];
        }
        if (depth[u] > depth[v]) std::swap(u, v);
        return std::max(ans, st.query(pos[u], pos[v]));
    }
};

int main() {
    HLDMax h(5);
    h.addEdge(0, 1); h.addEdge(0, 2); h.addEdge(1, 3); h.addEdge(1, 4);
    h.build({2, 4, 1, 7, 3});
    std::cout << h.queryPath(3, 2) << " ";
    h.setVal(1, 10);
    std::cout << h.queryPath(3, 2) << "\n"; // 7 10
    return 0;
}

</details>

---

Intermediate

3. Dynamic Path Sum + Subtree Sum Queries

Support point updates, path sum queries (u, v), and subtree sum queries (u) on the same HLD array!

Approach: Because dfs2 visits u's entire subtree contiguously, subtree u is [pos[u], pos[u] + sz[u] - 1]. Use a Fenwick Tree / Segment Tree for both path sums ($O(\log^2 n)$) and subtree sums ($O(\log n)$).

<details>

<summary>Show C++ Solution</summary>

#include <iostream>
#include <utility>
#include <vector>

struct SumSegTree {
    int n;
    std::vector<long long> seg;
    explicit SumSegTree(int n) : n(n), seg(2 * n, 0) {}
    void set(int idx, long long val) {
        for (seg[idx += n] = val; idx > 1; idx >>= 1) seg[idx >> 1] = seg[idx] + seg[idx ^ 1];
    }
    long long query(int l, int r) const {
        long long res = 0;
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res += seg[l++];
            if (r & 1) res += seg[--r];
        }
        return res;
    }
};

struct HLDSum {
    int n, timer = 0;
    std::vector<std::vector<int>> adj;
    std::vector<int> parent, depth, heavy, head, pos, sz;
    SumSegTree st;
    explicit HLDSum(int n) : n(n), adj(n), parent(n, -1), depth(n, 0),
                             heavy(n, -1), head(n, 0), pos(n, 0), sz(n, 0), st(n) {}
    void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); }
    int dfs1(int u, int p) {
        parent[u] = p; sz[u] = 1; int best = 0;
        for (int v : adj[u]) {
            if (v == p) continue;
            depth[v] = depth[u] + 1;
            int sub = dfs1(v, u); sz[u] += sub;
            if (sub > best) { best = sub; heavy[u] = v; }
        }
        return sz[u];
    }
    void dfs2(int u, int h) {
        head[u] = h; pos[u] = timer++;
        if (heavy[u] != -1) dfs2(heavy[u], h);
        for (int v : adj[u]) if (v != parent[u] && v != heavy[u]) dfs2(v, v);
    }
    void build(const std::vector<long long>& vals) {
        dfs1(0, -1); dfs2(0, 0);
        for (int i = 0; i < n; ++i) st.set(pos[i], vals[i]);
    }
    long long subtreeSum(int u) const { return st.query(pos[u], pos[u] + sz[u] - 1); }
    long long pathSum(int u, int v) const {
        long long ans = 0;
        while (head[u] != head[v]) {
            if (depth[head[u]] < depth[head[v]]) std::swap(u, v);
            ans += st.query(pos[head[u]], pos[u]);
            u = parent[head[u]];
        }
        if (depth[u] > depth[v]) std::swap(u, v);
        return ans + st.query(pos[u], pos[v]);
    }
};

int main() {
    HLDSum h(5);
    h.addEdge(0, 1); h.addEdge(0, 2); h.addEdge(1, 3); h.addEdge(1, 4);
    h.build({1, 2, 3, 4, 5});
    std::cout << h.pathSum(3, 2) << " " << h.subtreeSum(1) << "\n"; // 4+2+1+3=10, 2+4+5=11
    return 0;
}

</details>

4. Maximum Edge Weight on a Tree Path (SPOJ QTREE)

Given an edge-weighted tree, support updating an edge weight and querying the maximum edge weight on the path (u, v).

Approach: Push every edge weight down onto its deeper child node. In queryPath(u, v), stop before including the LCA by querying [pos[u] + 1, pos[v]] once u and v share a chain! Time: $O(\log^2 n)$.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <climits>
#include <iostream>
#include <tuple>
#include <utility>
#include <vector>

struct MaxST {
    int n;
    std::vector<int> seg;
    explicit MaxST(int n) : n(n), seg(2 * n, 0) {}
    void set(int idx, int val) {
        for (seg[idx += n] = val; idx > 1; idx >>= 1) seg[idx >> 1] = std::max(seg[idx], seg[idx ^ 1]);
    }
    int query(int l, int r) const {
        if (l > r) return 0;
        int res = 0;
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = std::max(res, seg[l++]);
            if (r & 1) res = std::max(res, seg[--r]);
        }
        return res;
    }
};

int main() {
    int n = 4;
    std::vector<std::tuple<int, int, int>> edges = {{0, 1, 5}, {1, 2, 8}, {1, 3, 3}};
    std::vector<std::vector<int>> adj(n);
    for (const auto& [u, v, w] : edges) { adj[u].push_back(v); adj[v].push_back(u); }

    std::vector<int> parent(n, -1), depth(n, 0), heavy(n, -1), head(n, 0), pos(n, 0);
    int timer = 0;
    auto dfs1 = [&](auto& self, int u, int p) -> int {
        parent[u] = p; int sz = 1, best = 0;
        for (int v : adj[u]) {
            if (v == p) continue;
            depth[v] = depth[u] + 1;
            int sub = self(self, v, u); sz += sub;
            if (sub > best) { best = sub; heavy[u] = v; }
        }
        return sz;
    };
    auto dfs2 = [&](auto& self, int u, int h) -> void {
        head[u] = h; pos[u] = timer++;
        if (heavy[u] != -1) self(self, heavy[u], h);
        for (int v : adj[u]) if (v != parent[u] && v != heavy[u]) self(self, v, v);
    };
    dfs1(dfs1, 0, -1); dfs2(dfs2, 0, 0);

    MaxST st(n);
    for (const auto& [u, v, w] : edges) {
        int child = (depth[u] > depth[v]) ? u : v;
        st.set(pos[child], w);
    }

    auto queryMaxEdge = [&](int u, int v) {
        int ans = 0;
        while (head[u] != head[v]) {
            if (depth[head[u]] < depth[head[v]]) std::swap(u, v);
            ans = std::max(ans, st.query(pos[head[u]], pos[u]));
            u = parent[head[u]];
        }
        if (depth[u] > depth[v]) std::swap(u, v);
        return std::max(ans, st.query(pos[u] + 1, pos[v])); // exclude LCA!
    };

    std::cout << queryMaxEdge(2, 3) << " " << queryMaxEdge(0, 3) << "\n"; // 8 5
    return 0;
}

</details>

---

Hard

5. Path Increment & Path Sum Queries (HLD + Lazy Segment Tree)

Support adding delta to every node on the path (u, v) and querying the sum of any path (a, b) in $O(\log^2 n)$ per operation.

Approach: Combine HLD with a lazy-propagating Segment Tree (rangeAdd and rangeSum) so each of the $O(\log n)$ heavy-chain segments is updated or queried in $O(\log n)$. Time: $O(\log^2 n)$.

<details>

<summary>Show C++ Solution</summary>

#include <iostream>
#include <utility>
#include <vector>

struct LazySegTree {
    int n;
    std::vector<long long> tree, lazy;
    explicit LazySegTree(int n) : n(n), tree(4 * n, 0), lazy(4 * n, 0) {}

    void push(int node, int l, int r) {
        if (lazy[node] == 0 || l == r) return;
        int m = (l + r) / 2;
        long long v = lazy[node];
        tree[2 * node] += v * (m - l + 1); lazy[2 * node] += v;
        tree[2 * node + 1] += v * (r - m); lazy[2 * node + 1] += v;
        lazy[node] = 0;
    }
    void add(int node, int l, int r, int ql, int qr, long long v) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) { tree[node] += v * (r - l + 1); lazy[node] += v; return; }
        push(node, l, r);
        int m = (l + r) / 2;
        add(2 * node, l, m, ql, qr, v);
        add(2 * node + 1, m + 1, r, ql, qr, v);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
    long long query(int node, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return tree[node];
        push(node, l, r);
        int m = (l + r) / 2;
        return query(2 * node, l, m, ql, qr) + query(2 * node + 1, m + 1, r, ql, qr);
    }
};

int main() {
    int n = 5;
    std::vector<std::vector<int>> adj(n);
    auto addEdge = [&](int u, int v) { adj[u].push_back(v); adj[v].push_back(u); };
    addEdge(0, 1); addEdge(0, 2); addEdge(1, 3); addEdge(1, 4);

    std::vector<int> parent(n, -1), depth(n, 0), heavy(n, -1), head(n, 0), pos(n, 0);
    int timer = 0;
    auto dfs1 = [&](auto& self, int u, int p) -> int {
        parent[u] = p; int sz = 1, best = 0;
        for (int v : adj[u]) {
            if (v == p) continue;
            depth[v] = depth[u] + 1;
            int sub = self(self, v, u); sz += sub;
            if (sub > best) { best = sub; heavy[u] = v; }
        }
        return sz;
    };
    auto dfs2 = [&](auto& self, int u, int h) -> void {
        head[u] = h; pos[u] = timer++;
        if (heavy[u] != -1) self(self, heavy[u], h);
        for (int v : adj[u]) if (v != parent[u] && v != heavy[u]) self(self, v, v);
    };
    dfs1(dfs1, 0, -1); dfs2(dfs2, 0, 0);

    LazySegTree st(n);
    auto pathAdd = [&](int u, int v, long long delta) {
        while (head[u] != head[v]) {
            if (depth[head[u]] < depth[head[v]]) std::swap(u, v);
            st.add(1, 0, n - 1, pos[head[u]], pos[u], delta);
            u = parent[head[u]];
        }
        if (depth[u] > depth[v]) std::swap(u, v);
        st.add(1, 0, n - 1, pos[u], pos[v], delta);
    };
    auto pathSum = [&](int u, int v) {
        long long ans = 0;
        while (head[u] != head[v]) {
            if (depth[head[u]] < depth[head[v]]) std::swap(u, v);
            ans += st.query(1, 0, n - 1, pos[head[u]], pos[u]);
            u = parent[head[u]];
        }
        if (depth[u] > depth[v]) std::swap(u, v);
        return ans + st.query(1, 0, n - 1, pos[u], pos[v]);
    };

    pathAdd(3, 2, 5); // nodes {3, 1, 0, 2} += 5
    pathAdd(4, 1, 3); // nodes {4, 1} += 3
    std::cout << pathSum(3, 4) << "\n"; // 3(5) + 1(8) + 4(3) = 16
    return 0;
}

</details>

---

Related Algorithms