An array of 1,000 values contains 500,500 different ranges you could be asked to sum. Storing an answer for each one sounds absurd, yet a single pass that saves just 1,000 running totals is enough to answer any of those 500,500 questions with one subtraction. How can a thousand stored numbers cover half a million answers?

Prefix Sums is a technique where you precompute the cumulative sum of an array. Each element in the resulting array represents the sum of all elements up to that index. Imagine keeping a running total of your daily expenses: with that running total in hand, you can quickly figure out how much you spent over any given period without summing each day individually. The expense log shares the technique's weakness too: correct one old entry and every total written after it is wrong. With prefix sums, you can answer range sum queries in constant time, as long as the underlying data holds still.

To create a prefix sum array, you iterate through the input array once. Start with the first element, and for every element after that, add its value to the running total. The result is an array where the value at each index represents the total sum from the start up to that index.

Build one by hand for [3, 1, 4, 1, 5]. The running total starts at 3, then climbs: 3 + 1 = 4, then 4 + 4 = 8, then 8 + 1 = 9, and finally 9 + 5 = 14. The prefix array is [3, 4, 8, 9, 14]: four additions, and that little table is the entire preprocessing bill for this input.

In general, for an array [a0, a1, a2, ..., an], the prefix sum array is: prefix[0] = a0, and for each i >= 1, prefix[i] = prefix[i - 1] + ai.

Once you have the prefix sum array, range sum queries become very efficient. To find the sum of elements between indices l and r, subtract the prefix sum at l - 1 from the prefix sum at r. If l is 0, the answer is just the prefix sum at r. Try it on the example from above: the input [3, 1, 4, 1, 5] produced the prefix array [3, 4, 8, 9, 14]. Before reading on, work out the sum of indices 1 through 3 using only two entries of the prefix array.

The answer is prefix[3] - prefix[0] = 9 - 3 = 6, which checks out against 1 + 4 + 1 = 6. Notice which entry got subtracted. You might reach for prefix[r] - prefix[l], but subtracting prefix[l] also removes arr[l] itself, the first element of the range you wanted. Subtracting prefix[l - 1] peels away everything before the range and nothing inside it. With that settled, each query goes from O(n) down to O(1) after the initial O(n) preprocessing.

Mechanically there are only two moves. One pass over the input builds the running totals, and after that, each range query is a single subtraction: the prefix sum just before the range comes off the prefix sum at its end. When the range starts at index 0, even the subtraction disappears, and the prefix entry is the answer by itself.

With one pass over the data for preprocessing and constant time per query after that, prefix sums hit a sweet spot between time and space complexity. The technique pays off most when you have multiple range queries on the same dataset.

The one blind spot is change. A prefix array assumes the data sits still: update a single element and every prefix total after it goes stale, forcing an O(n) rebuild before the next query can be trusted. When updates and range queries arrive interleaved, that weakness is exactly what segment trees were built to fix.

A lot of algorithmic problems boil down to computing the sum of a subarray or range. Repeatedly summing those portions gets expensive fast, which is why prefix sums show up so often. The pattern is common in dynamic programming and cumulative frequency analysis, and it pairs well with techniques like difference arrays for more advanced problems.

Prefix sums can drastically speed up solutions for a wide range of problems. Here are a few tips for using them well:

Before you start, quiz yourself on two things from this page: why does the range formula subtract prefix[l - 1] rather than prefix[l], and what happens to a prefix array the moment one element of the underlying data changes? If both answers come back quickly, you're ready. Prefix sums turn O(n) range queries into O(1) lookups, and a hashmap on top of them solves an entire class of "subarray sum equals X" problems in one pass. Work through these to internalize 1D prefix sums, 2D prefix sums, and the classic prefix-mod tricks for divisibility: