Heavy-Light Decomposition, in depth: heavy-first layout, path and subtree queries, edge weights and an iterative build

The problem: paths on a tree

Take a rooted tree with n nodes, a value on each node, and a stream of mixed operations: set the value of node u, add x to every node on the path from u to v, report the maximum on the path from u to v, report the sum over the subtree of u. Real instances include network topologies where a link's capacity changes and you need the bottleneck between two routers, organisational or file-system hierarchies with quota roll-ups, and competitive-programming problems with 10⁵ to 10⁶ nodes and as many queries.

The naive answer walks the path, which costs O(depth) per operation and degrades to O(n) on a long chain. Binary lifting handles static path aggregates in O(log n) but cannot absorb updates cheaply, because every jump table entry that covers the changed node goes stale. An Euler tour flattens subtrees into ranges but not paths. HLD gets both: O(log² n) per path operation and O(log n) per subtree operation, with point and range updates, using an ordinary segment tree underneath.

Heavy edges and the log n bound

For each internal node, call the child with the largest subtree its heavy child; the edge to it is heavy and every other child edge is light. Following heavy edges downward from any node that is not itself a heavy child traces a chain, and the chains partition the nodes.

The key fact: if the edge from p to a child c is light, then size(c) is at most size(p)/2. If it were larger, c would outweigh every sibling and would be the heavy child. So each light edge you cross going down at least halves the subtree size, and since sizes start at n and stay at least 1, any root-to-node path crosses at most log₂ n light edges. Every light edge starts a new chain, so any root-to-node path touches at most log₂ n + 1 chains, and a u-to-v path, which is two such paths joined at their lowest common ancestor, touches at most about 2 log₂ n + 1.

For n = 10⁶ that worst case is around 40 chains, and on random or bushy trees the observed number is usually a handful. Each chain fragment is one range query on the segment tree, costing O(log n), which is where the O(log² n) bound comes from.

One array for chains and subtrees

Assign each node a position pos[u] in a base array by running a depth-first traversal that always visits the heavy child first. Two properties fall out. First, each chain occupies consecutive positions, because after visiting u the traversal goes straight to its heavy child. Second, each subtree occupies the range pos[u] .. pos[u] + size[u] - 1, because any preorder DFS keeps subtrees contiguous. One array therefore serves both path queries and subtree queries, so you do not need a separate Euler tour.

Alongside pos you keep head[u], the top node of u's chain, parent[u] and depth[u]. Those four arrays plus a segment tree over the base array are the whole data structure. Memory is a few integers per node, which matters more than the asymptotics once n reaches the millions.

Building it without recursion

The build runs three passes with explicit stacks. The first records a DFS order with parents and depths. The second walks that order backwards, so children are finished before parents, accumulating sizes and picking heavy children. The third assigns positions: it pops a node, gives it the next position, pushes the light children, then pushes the heavy child last so it is popped next and the chain stays contiguous.

#include <bits/stdc++.h>
using namespace std;

struct HLD {
    int n;
    vector<vector<int>> g;
    vector<int> par, dep, heavy, head, pos, sz;
    explicit HLD(int n) : n(n), g(n), par(n, -1), dep(n, 0),
                          heavy(n, -1), head(n), pos(n), sz(n, 1) {}
    void add_edge(int a, int b) { g[a].push_back(b); g[b].push_back(a); }

    void build(int root) {
        vector<int> order, st{root};
        order.reserve(n);
        while (!st.empty()) {                      // pass 1: parents, depths
            int u = st.back(); st.pop_back();
            order.push_back(u);
            for (int v : g[u]) if (v != par[u]) {
                par[v] = u; dep[v] = dep[u] + 1; st.push_back(v);
            }
        }
        for (int i = n - 1; i > 0; --i) {          // pass 2: sizes, heavy child
            int u = order[i], p = par[u];
            sz[p] += sz[u];
            if (heavy[p] == -1 || sz[u] > sz[heavy[p]]) heavy[p] = u;
        }
        int cur = 0;                               // pass 3: heavy-first positions
        st = {root}; head[root] = root;
        while (!st.empty()) {
            int u = st.back(); st.pop_back();
            pos[u] = cur++;
            for (int v : g[u]) if (v != par[u] && v != heavy[u]) {
                head[v] = v; st.push_back(v);
            }
            if (heavy[u] != -1) { head[heavy[u]] = head[u]; st.push_back(heavy[u]); }
        }
    }
};

The build is O(n) time. It assumes the input is a tree that is connected and acyclic, with n - 1 edges; on a forest, run it once per component root and keep a shared position counter.

Path queries, updates and edge weights

To decompose the path between u and v, repeatedly take whichever endpoint has the deeper chain head, emit the range from that head to the endpoint, and jump to the head's parent. When both endpoints sit on the same chain, emit the final range between them. The shallower endpoint at that moment is the lowest common ancestor, so LCA comes for free.

// f(l, r) is called once per contiguous range, l <= r, inclusive.
template <class F>
int for_path(const HLD& h, int u, int v, bool edges, F f) {
    while (h.head[u] != h.head[v]) {
        if (h.dep[h.head[u]] < h.dep[h.head[v]]) swap(u, v);
        f(h.pos[h.head[u]], h.pos[u]);
        u = h.par[h.head[u]];
    }
    if (h.dep[u] > h.dep[v]) swap(u, v);           // u is now the LCA
    if (!edges) f(h.pos[u], h.pos[v]);
    else if (u != v) f(h.pos[u] + 1, h.pos[v]);    // skip the LCA's own slot
    return u;
}

template <class F>
void for_subtree(const HLD& h, int u, F f) { f(h.pos[u], h.pos[u] + h.sz[u] - 1); }

// usage with any segment tree exposing query(l, r) and update(l, r, x):
//   long long best = LLONG_MIN;
//   for_path(h, u, v, false, [&](int l, int r) { best = max(best, seg.query(l, r)); });
//   for_path(h, u, v, false, [&](int l, int r) { seg.update(l, r, delta); });

Edge weights. Many problems put values on edges, not nodes. Store the weight of the edge (parent[c], c) at the child, in slot pos[c]. Every edge on the u-v path is then represented by its lower endpoint, and the only node on the path whose slot does not belong to a path edge is the LCA, whose slot holds the edge above it. That is why the final range starts at pos[lca] + 1, and why it is empty when u equals v at the end. Forgetting this adds one extra edge to every query and is the most common HLD bug.

The underlying range structure is interchangeable. A lazy segment tree handles range add with range max; a Fenwick tree is enough for point updates with range sums. See segment trees and Fenwick trees for the array side.

Worked example: nine nodes by hand

Use the nine-node tree in the diagram, rooted at 1, with edges 1-2, 1-3, 2-4, 2-5, 3-6, 4-7, 4-8 and 6-9.

Now query the path from 8 to 9. The heads are 8 (depth 3) and 3 (depth 1), so 8 moves: emit range [4, 4] and jump to parent 4. The heads are now 1 (depth 0) and 3 (depth 1), so 9 moves: emit [6, 8], covering 3, 6 and 9, and jump to parent 1. Now 4 and 1 share head 1, so emit [0, 2], covering 1, 2 and 4. Together the three ranges hold nodes 8, 3, 6, 9, 1, 2 and 4, which is exactly the path 8-4-2-1-3-6-9, and the LCA is 1.

For edge weights on the same query, the last range becomes [1, 2]: slots for edges 1-2 and 2-4. The other ranges contribute edges 4-8, 1-3, 3-6 and 6-9, six edges in total, matching the six edges of the path. Tracing one small case by hand like this, then checking it against a brute-force path walk on random trees, catches nearly every off-by-one before it reaches a judge or production.

Cost in practice

In practice the log² factor is gentle: the chain count on real trees is small, and the first chain fragment is often long. If profiling shows path queries dominating, two refinements help. Queries that only aggregate (no updates) can use a sparse table per chain for O(1) ranges when the operation is idempotent, such as min, max or gcd, or per-chain prefix sums for sums, giving O(log n) per path. And a single segment tree over all chains has better cache behaviour than a separate tree per chain, which is why the layout above uses one global base array.

Failure modes

• Stack overflow on deep trees. A recursive DFS on a path-shaped tree of 10⁶ nodes exceeds default stack limits in C++, Java and Python. Use explicit stacks as above, or raise the limit deliberately and test the path-shaped worst case.
• Off-by-one on edge queries. Including pos[lca] counts the edge above the LCA. Test u equal to v (no edges) and u adjacent to v (one edge).
• Non-commutative aggregates. Max, sum and XOR do not care about direction, but path composition of functions, string hashes or matrix products do. Collect ranges from the u side and the v side separately, reverse the u side's order and orientation, then combine. Store both left-to-right and right-to-left aggregates in each segment node.
• Mixing original and position indices. The base array is indexed by pos[u], not u. Initialise it with base[pos[u]] = value[u]; point updates must also go through pos.
• Changing tree shape. HLD assumes a static tree. Adding or cutting edges invalidates sizes, heavy children and positions. For dynamic forests use a link-cut tree; for offline insertions, rebuild periodically.
• Root confusion. Subtree ranges are relative to the chosen root. If the problem changes the root per query, handle it with the standard rerooting case analysis rather than rebuilding.

Trade-offs against other tree techniques

Each of these has a home. For LCA alone, the comparison in LCA algorithms compared and the walkthrough in lowest common ancestor are simpler starting points. For subtree-only work, the Euler tour technique needs fewer arrays. Reach for HLD when both paths and updates are in the workload and the tree's shape is fixed.

What to do next

1. Implement the iterative build above and print pos, head and sz for the nine-node example; compare with the table.
2. Add a brute-force path walker and a random tree generator, and diff path sums for thousands of random queries, including path-shaped and star-shaped trees.
3. Plug in a lazy segment tree and support range add with path max; then switch to edge weights and re-run the tests with the pos[lca] + 1 rule.
4. Add a subtree query using pos[u] to pos[u] + sz[u] - 1 and verify it against a DFS sum.
5. Implement one non-commutative aggregate, such as path string hashing, to practise direction-aware merging.
6. Benchmark a path-shaped tree with 10⁶ nodes to confirm the build never recurses.