PrevNext
Rare
 0/12

Heavy-Light Decomposition

Author: Benjamin Qi

Path and subtree updates and queries.

Focus Problem – read through this problem before continuing!

Focus Problem – read through this problem before continuing!

Tutorial

Resources
cp-algo

For an alternate implementation, see below

CF

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

anudeep2011

explains what HLD is (but incomplete & overly complicated code)

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

A

There are better solutions than HLD (but it works)!

StatusSourceProblem NameDifficultyTags
GoldEasy
Show TagsHLD
GoldEasy
Show TagsHLD, PURS
PlatNormal
Show TagsHLD

B

HLD is intended.

StatusSourceProblem NameDifficultyTags
CSESEasy
Old GoldNormal
Show TagsHLD, PURS
YSNormal
Show TagsHLD, SegTree
CFHard
Show TagsHLD
TLXHard
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