PrevNext
Rare
 0/11

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-algoFor an alternate implementation, see below
anudeep2011explains 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
CFnot complete
Benqcomplete implementation following the above two articles with minor modifications

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

Problems

A

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

StatusSourceProblem NameDifficultyTagsSolution
GoldEasy
Show Tags

HLD

External Sol
GoldEasy
Show Tags

PURS, HLD

External Sol
PlatNormal
Show Tags

HLD

External Sol

B

HLD is intended.

StatusSourceProblem NameDifficultyTagsSolution
Old GoldNormal
Show Tags

HLD, PURS

External Sol
YSNormal
Show Tags

HLD, SegTree

Show Sketch
CFHard
Show Tags

HLD

Check CF
TLXHardView Solution
JOIHard
Show Tags

HLD

Show Sketch
JOIVery Hard
Show Tags

HLD

External Sol

Module Progress:

Give Us Feedback on Heavy-Light Decomposition!

PrevNext