PrevNext
Rare
 0/14

Heavy-Light Decomposition

Authors: Benjamin Qi, Andrew Cheng

Path and subtree updates and queries.

Focus Problem – try your best to solve this problem before continuing!

Focus Problem – try your best to solve this problem before continuing!

View Internal Solution

Tutorial

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

  • Update all nodes along the path from node xx to node yy.

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

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 xx to node yy on the tree can pass through at most O(logN)\mathcal{O}(\log N) light edges.

Proof

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 O(logN)\mathcal{O}(\log N) heavy paths on any path from an arbitrary node xx to an arbitrary node yy.

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 O(logN)\mathcal{O}(\log N) time.

Since there are at most O(logN)\mathcal{O}(\log N) heavy paths and O(logN)\mathcal{O}(\log N) light edges, computing the value on the path from node xx to node yy will take O(log2N+logN)\mathcal{O}(\log^2 N + \log N) = O(log2N)\mathcal{O}(\log^2 N) time. We can answer QQ queries in O(Qlog2N)\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:

C++

#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];
Resources
cp-algo

For an alternate implementation, see below

CF

blog + video for USACO Cowland. Binary jumping isn't necessary though.

Optional: Tree Queries in O(NQ)

This is why you don't set problems where Θ(QNlogN)\Theta(Q\sqrt N\log N) is intended ...

Implementations

Resources
CF
CF

not complete

Benq

complete implementation following the above two articles with minor modifications

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on GitHub.

Problems

StatusSourceProblem NameDifficultyTags
GoldEasy
Show TagsHLD, PURS
SPOJEasy
Show TagsHLD
GoldNormal
Show TagsHLD
PlatinumNormal
Show TagsHLD
HRNormal
Show TagsHLD, RURQ
Old GoldNormal
Show TagsHLD, PURS
YSNormal
Show TagsHLD, SegTree
CFHard
Show TagsHLD
CFHard
Show TagsHLD
TLXHard
Show TagsHLD
JOIHard
Show TagsHLD
JOIVery Hard
Show TagsHLD

Warning!

"Grass Planting" isn't submittable on the USACO website. Use this link to submit.

Module Progress:

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!

PrevNext