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]](swapu, vif not). - Query Segment Tree on
[pos[head[u]], pos[u]], then jumpu = parent[head[u]]. - Finally,
uandvare on the same chain: ensuredepth[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(otherwisevwould 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
- Segment Tree — the range-query engine inside HLD.
- Centroid Decomposition — alternative $O(\log n)$-depth tree decomposition for distance/path-counting queries.