Heavy-Light Decomposition
Reduce tree path queries to a logarithmic number of segment queries by carving the tree into heavy chains.
Heavy-Light Decomposition
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Heavy-light decomposition is the standard reduction from tree path queries to array interval queries. It breaks the tree into a small number of heavy chains, then uses a segment tree or Fenwick tree on the flattened order.
When a problem keeps asking for values on paths between arbitrary vertices, HLD is often the first general technique that turns the tree into something interval-based and manageable.
When to Use It
Use it when:
queries are on paths between arbitrary vertices,
path answers can be merged associatively,
the tree is static,
you can maintain each chain with a range-query structure.
It is usually unnecessary for pure subtree queries, where an Euler-tour flattening alone often solves the problem.
Core Idea
For each vertex, choose one child with maximum subtree size as its heavy child. Heavy edges link a vertex to its heavy child; the other edges are light.
Following heavy edges downward forms vertex-disjoint chains. Every vertex belongs to exactly one chain, and each chain becomes a contiguous interval in the flattened array.
Key Insight
The crucial fact is not the chain picture itself. The crucial fact is: every time a root-to-node path crosses a light edge, the remaining subtree size at least halves.
That means a root-to-node path crosses only \(O(\log n)\) light edges. Therefore a path between two arbitrary vertices breaks into only \(O(\log n)\) heavy-chain segments.
That is the entire reason HLD is useful: one hard tree path becomes a logarithmic number of easy interval queries.
Operations / Main Technique
The usual workflow is:
first DFS: compute subtree sizes and choose the heavy child,
second DFS: assign each vertex a chain head and a position in the flattened array,
build a segment tree over the flattened vertex values,
answer a path query by repeatedly climbing the deeper chain head.
Worked path query.
While \(\texttt{head[u]} \neq \texttt{head[v]}\), query the deeper chain segment, jump that endpoint to the parent of its chain head, and continue. Once both vertices are on the same chain, finish with one final interval query.
Correctness Intuition
Every tree edge is either heavy or light, so any path is partitioned into consecutive chain segments with no overlap and no gaps. Each of those chain segments is contiguous in the flattened array by construction.
Therefore the path answer is exactly the merge of those segment-tree answers. The logarithmic number of segments comes from the ``light edge halves the subtree'' argument.
Complexity Analysis
preprocessing: \(O(n)\),
point update: \(O(\log n)\),
path query with a segment tree: \(O(\log^2 n)\),
subtree query in the same flattening: \(O(\log n)\),
memory: \(O(n)\) plus the inner range structure.
The extra logarithm in path queries comes from doing \(O(\log n)\) chain jumps and paying \(O(\log n)\) per segment tree query.
Implementation
The reference code stores values on vertices and supports:
build from initial vertex values,
point assignment,
path-sum query,
subtree-sum query.
That is the version I want to trust first. For edge-value problems, the common trick is to store each edge's value on its deeper endpoint and adjust the final same-chain interval accordingly.
Common Pitfalls
Forgetting whether values live on vertices or on edges.
Comparing depths of vertices instead of depths of chain heads in the climb loop.
Getting the final same-chain interval off by one.
Reusing subtree intervals without checking that the flattening order is compatible.
Writing a correct segment tree but assigning
headorposin the wrong DFS order.
Variants / Extensions
edge-value HLD,
path updates via lazy segment trees,
path max, min, xor, or custom associative states,
mixing path queries with subtree queries in the same flattened order,
HLD plus LCA or binary lifting for related tree tasks.
Compared with link-cut trees, HLD wins on simplicity when the represented tree is static.
Practice Problems
Path sum or path maximum queries with point updates.
Tree problems that mix subtree sums and arbitrary path queries.
Static-tree tasks where dynamic-tree machinery would be unnecessary.
References
Code
Contest-ready reference implementation for the idea explained above.
struct SegTree {
int n;
vector<long long> tree;
SegTree() : n(0) {}
void build(const vector<long long>& values) {
n = 1;
while (n < (int)values.size()) n <<= 1;
tree.assign(2 * n, 0);
for (int i = 0; i < (int)values.size(); ++i) tree[n + i] = values[i];
for (int i = n - 1; i > 0; --i) tree[i] = tree[i << 1] + tree[i << 1 | 1];
}
void point_set(int pos, long long value) {
pos += n;
tree[pos] = value;
for (pos >>= 1; pos > 0; pos >>= 1) {
tree[pos] = tree[pos << 1] + tree[pos << 1 | 1];
}
}
long long range_sum(int left, int right) const {
long long answer = 0;
for (left += n, right += n; left <= right; left >>= 1, right >>= 1) {
if (left & 1) answer += tree[left++];
if (!(right & 1)) answer += tree[right--];
}
return answer;
}
};
struct HeavyLightDecomposition {
int n, current_pos;
vector<vector<int>> graph;
vector<int> parent, depth, heavy, head, pos, subtree;
vector<long long> values, base;
SegTree seg;
HeavyLightDecomposition() : n(0), current_pos(0) {}
explicit HeavyLightDecomposition(int n) { init(n); }
void init(int n_) {
n = n_;
current_pos = 0;
graph.assign(n, {});
parent.assign(n, -1);
depth.assign(n, 0);
heavy.assign(n, -1);
head.assign(n, 0);
pos.assign(n, 0);
subtree.assign(n, 0);
values.assign(n, 0);
base.assign(n, 0);
}
void add_edge(int u, int v) {
graph[u].push_back(v);
graph[v].push_back(u);
}
int dfs_size(int v, int p) {
parent[v] = p;
subtree[v] = 1;
int best_subtree = 0;
for (int to : graph[v]) {
if (to == p) continue;
depth[to] = depth[v] + 1;
int child_size = dfs_size(to, v);
subtree[v] += child_size;
if (child_size > best_subtree) {
best_subtree = child_size;
heavy[v] = to;
}
}
return subtree[v];
}
void dfs_decompose(int v, int chain_head) {
head[v] = chain_head;
pos[v] = current_pos;
base[current_pos++] = values[v];
if (heavy[v] != -1) {
dfs_decompose(heavy[v], chain_head);
}
for (int to : graph[v]) {
if (to == parent[v] || to == heavy[v]) continue;
dfs_decompose(to, to);
}
}
void build(const vector<long long>& initial_values, int root = 0) {
values = initial_values;
fill(heavy.begin(), heavy.end(), -1);
depth[root] = 0;
current_pos = 0;
dfs_size(root, -1);
dfs_decompose(root, root);
seg.build(base);
}
void point_set(int v, long long value) {
seg.point_set(pos[v], value);
}
long long query_path(int a, int b) const {
long long answer = 0;
while (head[a] != head[b]) {
if (depth[head[a]] < depth[head[b]]) swap(a, b);
answer += seg.range_sum(pos[head[a]], pos[a]);
a = parent[head[a]];
}
if (depth[a] > depth[b]) swap(a, b);
answer += seg.range_sum(pos[a], pos[b]);
return answer;
}
long long query_subtree(int v) const {
return seg.range_sum(pos[v], pos[v] + subtree[v] - 1);
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.