Range Query Patterns

Range queries are about picking the cheapest structure that satisfies your update pattern.

Think range query structures when you see:

• Repeated sum/min/max over subranges
• “Count inversions / smaller elements to the left”
• Static array with many O(1) min queries
• Point updates + prefix aggregates

Quick Recognition Cheat Sheet

If you see…	Think…	Why
Prefix sums, no updates	Prefix Sum array	O(n) build, O(1) query
Point update + prefix sum	Fenwick tree	Tiny code, O(log n) both
Immutable + O(1) min/max	Sparse table	O(n log n) build, O(1) query
Range update + range aggregate	Segment tree lazy	Full flexibility
Kth order statistic updates	Fenwick over values	Binary search on the BIT

Pattern Table

Structure	Build	Query	Update	Code size
Prefix sum	O(n)	O(1)	O(n) ❌	tiny
Fenwick (BIT)	O(n log n)	O(log n)	O(log n)	~15 lines
Sparse table	O(n log n)	O(1)	none ❌	~20 lines
Segment tree	O(n)	O(log n)	O(log n)	~50 lines

Mental Trigger

No updates → prefix/sparse. Updates → Fenwick. Range updates → segment tree lazy.

Decision Guide

Static data?
    ├─ sum only        → Prefix Sum
    └─ min/max/gcd     → Sparse Table

Dynamic data?
    ├─ point add + prefix sum   → Fenwick Tree
    ├─ need min/max too         → Segment Tree
    └─ range updates            → Segment Tree + Lazy