Dynamic operations that mix path updates and queries on a tree defeat simple prefix‑sum or difference‑based preprocessing. Heavy‑light decomposition (HLD) assigns each vertex to a heavy path and gives every path, as well as every complete subtree, a contiguous interval in a preorder. By flattening these intervals onto a segment tree, HLD reduces both path and subtree queries to standard range queries.

Core Concepts

Choose a rooted tree. For each node, the heavy child is the child with the largest subtree; ties are broken arbitrarily. All other children are light children. An edge to a heavy child is a heavy edge, and an edge to a light child is a light edge. A heavy path is a maximal chain formed by consecutive heavy edges. Every leaf that is not a heavy child forms a one‑node heavy path.

Building the Decomposition (Two DFS)

Two depth‑first traversals collect the information needed to map the tree to a segment tree.

First DFS — Subtree Sizes and Heavy Child

Record the parent, depth, subtree size, and heavy child for each vertex.

int parent[N], depth[N], sz[N], heavy[N];
vector<int> adj[N];

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

Second DFS — Heavy Path Labels and Segment Tree Positions

Assign each vertex a position pos[u] in the segment tree, store the reverse mapping rev[pos], and record the head of its current heavy path.

int head[N], pos[N], rev[N], timer;

void dfs2(int u, int h) {
  head[u] = h;
  pos[u] = ++timer;
  rev[timer] = u;
  if (heavy[u])                     // continue the heavy path
    dfs2(heavy[u], h);
  for (int v : adj[u]) {
    if (v == parent[u] || v == heavy[u]) continue;
    dfs2(v, v);                     // start a new heavy path
  }
}

Path and Subtree Operations

Once the positions are assigned,192 every heavy path corresponds to a contiguous range [pos[head[x]], pos[x]]. Likewise, the subtree rooted at x corresponds to the interval [pos[x], pos[x] + sz[x] - 1].

Lowest Common Ancestor (LCA)

While head[x] != head[y], move the vertex with the deeper head upward: let x become parent[head[x]]. Afterwards, the LCA is the vertex with the smaller depth.

int lca(int x, int y) {
  while (head[x] != head[y]) {
    if (depth[head[x]] < depth[head[y]]) swap(x, y);
    x = parent[head[x]];
  }
  return depth[x] < depth[y] ? x : y;
}

Path Queries / Updates

To query or update a path between u and v, jump up the heavy chains similarly to the LCA, and apply the15 segment tree operation on the interval [pos[head[u]], pos[u]] whenever head[u] != head[v]. After the loop,16 a final operation on the range between pos[u] and pos[v] handles the remanider.

void update_path(int u, int v, int val) {
  while (head[u] != head[v]) {
    if (depth[head[u]] < depth[head[v]]) swap(u, v);
    segtree_update(pos[head[u]], pos[u], val);
    u = parent[head[u]];
  }
  if (depth[u] > depth[v]) swap(u, v);
  segtree_update(pos[u], pos[v], val);
}

Subtree Operations

Because the pos values of a subtree are consecutive, a subtree query or update is a single segment tree call:

void update_subtree(int x, int val) {
  segtree_update(pos[x], pos[x] + sz[x] - 1, val);
}

Notes on Changing the Root

if the root of the tree is changed, the heavy‑child relationships may completely change, requiring a new decomposition. In rare situations where17 frequent rerooting is needed, Euler‑tour techniques or Link‑Cut trees are more suitable.