Prefix Sum
Suppose you are handed an array and asked for the sum of the elements between index i and index j. One query is easy: loop from i to j and add. But now imagine thousands of such queries over the same array, or a search that inspects the sum of every possible subarray. Recomputing each range from scratch costs O(n) per query, and the work piles up fast.
Prefix sum removes that repetition. You spend O(n) once to precompute running totals, and afterward every range sum collapses into a single subtraction that runs in O(1), no matter how wide the range.
If you prefer video, here is a short walkthrough from the AlgoMonster channel:
The running-totals transformation
A prefix sum turns an array into a new array of running totals. For an input array arr of length n, build a prefix array of length n + 1:
prefix[0] = 0
prefix[k] = arr[0] + arr[1] + ... + arr[k-1]
Each entry is the previous total plus one more element, so a single pass builds the whole thing:
prefix[k] = prefix[k-1] + arr[k-1]
The leading prefix[0] = 0 is the sum of zero elements. That extra slot is what makes the range math below land exactly on the boundaries, which is why prefix has one more cell than arr.
Because each prefix value stacks one more element onto the last, the running totals only grow. Drawn as bars, every step is the previous total (blue) plus one new element (amber):
Any range sum is one subtraction
The sum of the subarray from index i up to (but not including) j is prefix[j] - prefix[i]. prefix[j] is the total of everything before j, and prefix[i] is the total of everything before i, so subtracting throws away the front you did not ask for and leaves the middle. Here it is with real numbers:
The answer never depends on how many elements sit between i and j, so the query is O(1) whether the range spans two elements or two million. Building prefix costs O(n) time and O(n) space, which pays off as soon as the array is queried more than a couple of times.
Try it yourself
Build the prefix array one element at a time, then switch to query mode and slide the boundaries to watch any subarray sum resolve into a single subtraction.
Reading the widget
In build mode, watch a single column. The new array element (amber, top row) and the previous running total (amber, bottom row) add up to fill the next prefix cell (green). Repeat across the array and the final cell holds the total of everything.
In query mode, the green cells are the subarray you selected. The formula touches only two prefix cells: prefix[j] (indigo) is the running total up to the end of your range, and prefix[i] (amber) is the running total up to the start. Their difference is the answer, and it stays one subtraction no matter how many green cells lie between them.
Watch the boundaries
The one place prefix sums trip people up is the off-by-one at the edges. Keep three facts straight: prefix has length n + 1, prefix[0] is 0, and sum(arr[i..j-1]) = prefix[j] - prefix[i] uses an exclusive right index j. If a problem hands you an inclusive right index r, translate it to prefix[r + 1] - prefix[i].
When to reach for it
Prefix sums fit whenever you need repeated range sums over a fixed array, or when an algorithm searches across subarray boundaries. For a single one-off sum, a plain loop is simpler; the prefix array earns its O(n) setup only once the same array is queried many times.
The idea generalizes past addition: the same trick gives prefix products, prefix XOR, and 2D grids where you precompute rectangle sums. A common upgrade pairs the running sum with a hash map — you record each total as you scan and ask whether a complementary value appeared earlier, turning a subarray search into O(1) lookups.
Now apply the pattern to the problems in this section:
- Prefix Sum Technique Explained — find a subarray with a target sum using the running-sum-plus-hash-map form.
- Range Sum Query - Immutable — the canonical precompute-once, answer-many setup.
- Product of Array Except Self — the same prefix idea applied to products from both directions.