Skip to content

Heavy-Light Decomposition Ladder

HLD practice should make path decomposition feel systematic instead of magical. The main goal is to understand why one tree path becomes only a few segment intervals.

Who This Is For

Use this ladder if:

  • tree path queries still tempt you into walking the path directly
  • LCA is comfortable, but path aggregates still feel missing
  • segment trees are fine alone, but combining them with trees is still shaky

Warm-Up

  • heavy child selection
  • chain-head reasoning
  • flattening a tree into one base array

Target skill:

  • explain the decomposition before writing the code

Core

  • point update plus path maximum
  • point update plus path sum
  • same-chain versus cross-chain handling

Target skill:

  • decompose any path into O(log n) contiguous segments without getting lost

Stretch

  • edge-valued variants
  • path updates with lazy propagation
  • compare HLD against Euler-tour flattening for subtree-only tasks

Target skill:

  • know when HLD is the right hammer and when it is overkill

Retrieval Layer

Exit Criteria

You are ready to move on when:

  • you can compute heavy, head, and pos confidently
  • you know why the chain count is only O(log n)
  • you can debug same-chain and cross-chain logic separately

External Practice