Skip to content

Interval Tree Hot Sheet

Use this page when one live set of intervals must answer online overlap queries, and the real invariant is not one fixed coordinate array.

Do Not Use When

  • the intervals stay pairwise disjoint and predecessor/successor already closes the whole query -> Heaps And Ordered Sets
  • all queries are offline -> Offline Tricks
  • the real structure is a piecewise-constant interval partition under range assign -> ODT / Chtholly
  • the real query is coverage/count/aggregate over a fixed line -> Segment Tree

Choose By Signal

  • one live interval set with insert / erase / any-overlap query -> Interval Tree
  • already-disjoint intervals and one neighbor check is enough -> ordered set
  • piecewise-constant runs under assign -> ODT
  • aggregate coverage on one fixed coordinate universe -> Segment Tree

Core Invariants

  • intervals are usually treated as half-open [l, r)
  • BST order is by (l, r)
  • every node stores subtree max_r
  • left subtree can be skipped when left.max_r <= ql
  • right subtree can be skipped when current.l >= qr

Main Traps

  • mixing closed and half-open overlap semantics
  • forgetting to recompute max_r after every structural change
  • using this when the real task is offline or aggregate-by-coordinate
  • pretending interval trees are the default CP route whenever a statement mentions intervals

Exact Starter Route

Reopen Paths