Segment Tree Patterns

A segment tree stores aggregate answers for ranges in a binary tree so any range can be queried in O(log n) and updated in O(log n).

Think Segment Tree when you see:

• Range sum/min/max/gcd queries with point updates
• Range updates + range queries together
• Queries over dynamic data (prefix sums break here)
• Counting/inversion problems on ranges

Quick Recognition Cheat Sheet

If you see…	Think…
Static array + many range sums	Prefix sums (simpler!)
Updates and range queries	Segment tree
Range update + range query	Lazy propagation
Min/max/GCD over changing ranges	Segment tree (swap combiner)
“How many elements < x in [l..r]“	Merge-sort tree / offline

Pattern Table

Pattern	Typical Questions	Trigger
Point Update	Range Sum Query Mutable	Update one index, query range
Range Update	Range Addition	Add to [l..r], query later
Lazy Propagation	Assign/add on ranges	Defer work with tags

Mental Trigger

Query + Update both needed → Segment Tree. Static data → prefix sum.

Decision Guide

Only prefix queries, no updates
        ↓
   Prefix Sum array  ← stop, don't over-engineer

Point updates + range aggregate
        ↓
   Basic Segment Tree (or Fenwick if just sums)

Range updates + range aggregates
        ↓
   Segment Tree + Lazy Propagation

Immutable array + O(1) min/max queries
        ↓
   Sparse Table (see Range Query section)