Skip to content

Subtree Queries Hot Sheet

Use this page when the tree is static, the query touches one whole subtree, and you want to flatten that subtree into one interval before choosing a range structure.

Do Not Use When

  • the query is on an arbitrary path u -> v, not one subtree
  • the real work is combining child states rather than querying a flattened interval
  • you only need ancestor checks, so tin/tout alone is enough
  • the tree itself changes online

Choose By Signal

Core Invariants

  • this lane uses a single-entry DFS order, not the full Euler tour
  • tin[u] is the flattened position of node u
  • the subtree of u is exactly the half-open interval [tin[u], tout[u])
  • tout[u] - tin[u] equals the subtree size
  • node-value update on u becomes one point update at tin[u]

Main Traps

  • confusing subtree flattening with the full Euler tour used for some LCA reductions
  • mixing inclusive subtree ranges from the statement with the half-open internal interval [tin[u], tout[u])
  • reaching for HLD when the query is subtree-only
  • forgetting that point assignment on the original tree becomes a point delta update on Fenwick

Exact Starters In This Repo

Reopen Paths