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. With prefix sums, you can answer range sum queries in constant time.

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.

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.

Each query goes from O(n) down to O(1) after the initial O(n) preprocessing.

The idea behind prefix sums is straightforward. You iterate over the original array once to build a new array where each element is a cumulative total. That precomputation captures the sum from the start of the array up to any index, ready to use later.

When a range query comes in, the algorithm gets the sum over that range by subtracting the prefix sum just before the start of the range from the prefix sum at the end. There's no need to walk the elements for each query. If the query starts at index 0, no subtraction is needed at all: the prefix sum directly gives the answer.

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.

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:

Prefix sums turn O(n) range queries into O(1) lookups, and pairing them with a hashmap unlocks an entire class of "subarray sum equals X" problems. Work through these to internalize 1D prefix sums, 2D prefix sums, and the classic prefix-mod tricks for divisibility: