Suppose we want to support the following operations on a tree:

1. Update all nodes along the path from node $x$ to node $y$.
2. Query 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 (HLD) supports both of these operations efficiently. Naively performing these operations can be slow on large trees, but HLD decomposes the tree into paths to allow updates and queries in logarithmic time.

Tutorial

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 the 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 a maximal and contiguous path formed by only heavy edges. The set of all heavy paths spans every node in the tree.

Note that there is no notion of "light paths" in HLD; light edges simply connect heavy paths to each other.

Properties

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

A heavy path can only be broken by crossing a light edge; otherwise, the heavy path would simply continue on. Because of this, we know there are at most ${O}(\log N)$ heavy paths on any path from an arbitrary node $x$ to an arbitrary node $y$.

Additionally, by using a Segment Tree (or similar structure), we can process queries on a contiguous segment of any heavy chain in $\mathcal{O}(\log N)$ time.

Since the process requires performing $\mathcal{O}(\log N)$ Segment Tree operations, the total time for a path query or update is $\mathcal{O}(\log N) \times \mathcal{O}(\log N) = \mathcal{O}(\log^2 N)$. Therefore, we can answer $Q$ queries in $\mathcal{O}(Q \log^2 N)$ time.

Here's an animation of how the algorithm works:

Implementation

Below is an example implementation of Heavy Light Decomposition based on the resources above. See the solution below, as well as the solutions for Subtrees & Paths and Query on a tree again!, for examples of how this implementation can be used.

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

template <class T, bool VALS_IN_EDGES> class HLD {
  private:
	int N, R, tim = 0;  // n, root node, time
	vector<vector<int>> adj;
	vector<int> par, siz, depth, rt, pos;  // parent, size, depth, root, position arrays
	LazySegtree<T> segtree;                // Modify as needed

Path Queries II

Explanation

We can label each edge as either heavy or light, then use a segment tree to keep track of the maximum value in each heavy chain.

Now, to change the value at node $i$ to $x$, we can just update the value in the segment tree. To query the maximum value in the path from $a$ to $b$, we first find the Lowest Common Ancestor. We combine the path from $a$ to $lca(a,b)$ and the path from $b$ to $lca(a,b)$ to find our answer.

Implementation

Time Complexity: $\mathcal{O}(\log^2N)$ per query

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

 Code Snippet: Segment Tree (Click to expand)

 Code Snippet: HLD (Click to expand)

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

Problems