Cumulative totals up front
A prefix sum array stores, at each position, the total of all elements up to and including that index. Building it costs one linear pass, and once you have it any range sum reduces to a single subtraction.
The range query trick
To get the sum of a contiguous range from index i to index j, you take the prefix total at j and subtract the prefix total just before i. Two array lookups and one subtraction answer a query that would otherwise scan the whole range.
- Build once in linear time.
- Query many times in constant time each.
- Use a leading zero sentinel so ranges starting at index zero need no special case.
A powerful pairing
Prefix sums combine beautifully with a hash map for problems like counting subarrays that sum to a target. As you sweep, you look up how many earlier prefixes would complete a valid range ending at the current position.
Key idea
Precomputing cumulative totals lets any range sum collapse into one subtraction of two prefixes, trading a one time linear build for constant time queries afterward.