Range Query Techniques

A cross-cutting branch: not a family of structures but a family of strategies for answering many questions about subarrays, subtrees and submatrices.

Choosing a technique

Situation	Use
Static array, idempotent op (min/max/gcd)	Sparse Table
Point update, prefix-invertible op	Fenwick Tree
Point/range update, any associative op	Segment Tree
Range update with a weird op	Segment Tree Beats
Offline queries, no updates	Mo’s Algorithm
Queries interleaved with updates, offline	Offline + CDQ / BIT sweep
Historic versions	Persistent Segment Tree
Nothing else fits, n ≤ 2·10^5	Sqrt Decomposition

Techniques

• Prefix Sums and Difference Arrays
• Range Minimum Query
• Mo’s Algorithm
• Mo’s Algorithm on Trees
• Offline Query Processing
• CDQ Divide and Conquer
• Parallel Binary Search
• Sqrt Decomposition on Queries
• K-th Order Statistics on Ranges
• 2D and Higher-Dimensional Queries

See also: Data Structures · DSU on Tree