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.

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 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:

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