Heavy-Light Decomposition

Tutorial

Suppose that you want to support the following operations on a tree:

• Update all nodes along the path from node $x$ to node $y$.

• Find the sum, maximum, minimum (or any other operation that satisfies the associative property) along the path from node $x$ to node $y$.

Heavy Light Decomposition (or HLD) supports both operations efficiently.

Definitions

• A heavy child of a node is the child with the largest subtree size rooted at the child.
• A light child of a node is any child that is not a heavy child.
• A heavy edge connects a node to its heavy child.
• A light edge connects a node to any of its light children.
• A heavy path is the path formed by a collection heavy edges.
• A light path is the path formed by a collection light edges.

Properties

Any path from node $x$ to node $y$ on the tree can pass through at most $\mathcal{O}(\log N)$ light edges.

Since a heavy path can only be broken by a light edge (or else the edge will be a part of the heavy path), we can know that there are at most $\mathcal{O}(\log N)$ heavy paths on any path from an arbitrary node $x$ to an arbitrary node $y$.

In addition, by using segment trees (or any other RURQ data structure) we can calculate the value of any consecutive interval on any heavy path in $\mathcal{O}(\log N)$ time.

Since there are at most $\mathcal{O}(\log N)$ heavy paths and $\mathcal{O}(\log N)$ light edges, computing the value on the path from node $x$ to node $y$ will take $\mathcal{O}(\log^2 N + \log N)$ = $\mathcal{O}(\log^2 N)$ time. We can answer $Q$ queries in $\mathcal{O}(Q \log^2 N)$ time.

Here's an animation of how the algorithm works:

We can solve the focus problem "Path Queries II" using Heavy Light Decomposition:

Copy
#include "bits/stdc++.h"
using namespace std;

const int N = 2e5 + 5;
const int D = 19;
const int S = (1 << D);

int n, q, v[N];
vector<int> adj[N];

Implementations

Problems