Authors: Benjamin Qi, Andrew Cheng
Path and subtree updates and queries.
Focus Problem – try your best to solve this problem before continuing!
Suppose that you want to support the following operations on a tree:
Update all nodes along the path from node to node .
Find the sum, maximum, minimum (or any other operation that satisfies the associative property) along the path from node to node .
Heavy Light Decomposition (or HLD) supports both operations efficiently.
- 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.
Any path from node to node on the tree can pass through at most 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 heavy paths on any path from an arbitrary node to an arbitrary node .
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 time.
Since there are at most heavy paths and light edges, computing the value on the path from node to node will take = time. We can answer queries in time.
Here's a helpful animation of how the algorithm works:
We can solve the focus problem "Path Queries II" using Heavy Light Decomposition:
#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];
Show TagsHLD, PURS
Show TagsHLD, RURQ
Show TagsHLD, PURS
Show TagsHLD, SegTree
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!