Range Queries
Precomputing enough partial answers that any interval can be assembled in log n steps or fewer.
A range query asks something about a contiguous slice: the sum of a[l..r], the minimum, the maximum. Answering one by scanning costs r - l + 1 reads, so q of them cost O(nq). That product is the number every structure in this category exists to bring down.
They all strike the same bargain: spend time and memory up front on partial answers, then build any interval out of a few of them. A prefix sum stores every answer that starts at index 0, so a range is one subtraction. A sparse table stores the minimum of every window whose length is a power of two, so a range is the better of two overlapping blocks. A segment tree stores an answer per node, so any interval is covered by O(log n) whole nodes, and a Fenwick tree packs the same idea into one array where cell i covers a run as long as its lowest set bit.
What separates them is updates. A prefix sum and a sparse table are read-only: change one element and the precomputation is rebuilt. A segment tree and a Fenwick tree take a point update in O(log n), because any one element appears in only log n of their stored answers. When an update covers a whole range, lazy propagation parks it on the node that covers that range and pushes it down only when a later query descends through.
After this you can
- Choose between a prefix sum, a sparse table, a Fenwick tree and a segment tree from the read and write mix
- Answer a rectangle sum on a grid with four lookups using inclusion and exclusion
- Trace a segment tree query and count the nodes it stops at rather than descends into
- Say what the lowest set bit does in a Fenwick tree's two walks
- Decide when a range update needs lazy propagation instead of repeated point updates
prefix[7] = prefix[6] + a[7] = 25 + 6 = 31.
In this order
- Prefix SumStore running totals once, and any range sum becomes two lookups and a subtraction.
- Range Minimum QueryThe minimum of a range, answered from O(log n) nodes of a min tree.
- 2D Prefix SumP[i][j] = a + P[i-1][j] + P[i][j-1] - P[i-1][j-1]; any rectangle sum in O(1).
- Difference MatrixFour corner writes per rectangle, then a prefix pass along rows and down columns.
- Sparse Table Build and Queryk = floor(log2(len)); the answer is min of the windows starting at l and ending at r, overlap harmless.
- Segment Tree Query and UpdateA query takes whole nodes inside the range and splits only the ones on its edge.
- Lazy PropagationRange updates are stored on nodes and pushed to children only when needed.
- Fenwick Update and QueryQuery walks i to i minus lowbit(i). Update walks i to i plus lowbit(i).
Where people go wrong
Rebuilding a prefix sum after every update
Changing one element invalidates every prefix after it, so an update is O(n). If updates and queries are interleaved, the prefix sum has already lost to a Fenwick tree, which does both in log n.
Overlap is only free for some operations
A sparse table answers a minimum with two blocks that overlap, because taking the minimum of a value twice changes nothing. A sum counts the overlap twice, so sums need the disjoint nodes of a segment tree or the Fenwick walk instead.
Off by one in the inclusion and exclusion
A rectangle sum subtracts the row above and the column to the left, then adds back the corner that was subtracted twice, and all three use index i - 1 or j - 1. Most 2D bugs are in those indices rather than in the structure.
Or a different category
Array Algorithms and Techniques
One pass answers the question, and no interval is ever asked about twice.
Data Structures
You want the structures themselves: how a segment tree, a Fenwick tree or a sparse table is built and stored.