Prefix Sum: Complete Guide with Range Query Examples

Coding Patterns - Guide to 30 Core Algorithm Patterns

Prefix sum is the pattern you reach for when a problem keeps asking about sums of ranges. Sum from index 2 to index 5. Sum from index 0 to index 3. Sum of the whole array. Answering each request by adding elements one by one costs

O(N)

per query, and that cost adds up fast across many queries. The prefix sum trick computes one running total once, then answers every range sum with a single subtraction.

Definition: build an array where prefix[i] holds the sum of the first i elements of the input. The sum of nums[left..right] is then prefix[right + 1] - prefix[left], which is one subtraction no matter how long the range is.

Real-World Analogy

You keep a spreadsheet of monthly spending with a running total column. By December, the last row shows what you spent all year. Someone asks what you spent from March through July. You do not reopen the receipts. You read the July running total, subtract the February running total, and the difference is exactly the five-month sum. The running total column is the prefix array. The one subtraction is the range query. As long as the numbers do not change, that single column answers every month-range question for the rest of the year.

Visual Explanation

Building the prefix array is one pass that carries the running total forward. Each new slot in prefix takes the previous total and adds the next input element.

    graph TD
    P0["prefix[0] = 0"]
    P1["prefix[1] = prefix[0] + nums[0] = 0 + 3 = 3"]
    P2["prefix[2] = prefix[1] + nums[1] = 3 + 1 = 4"]
    P3["prefix[3] = prefix[2] + nums[2] = 4 + 4 = 8"]
    P4["prefix[4] = prefix[3] + nums[3] = 8 + 2 = 10"]
    P5["prefix[5] = prefix[4] + nums[4] = 10 + 5 = 15"]
    P0 --> P1 --> P2 --> P3 --> P4 --> P5
    Q["Query: sum nums[2..4] = prefix[5] - prefix[2] = 15 - 4 = 11"]
    P5 -.-> Q

Two details matter here. The leading 0 is not filler. It makes prefix[0] a valid subtraction for queries that start at index 0, so those queries need no special handling. And in the query step, prefix[5] already contains the sum of the first five elements, nums[0..4]. Subtracting prefix[2], the sum of nums[0..1], removes everything before the range and leaves exactly nums[2..4].

The same idea scales to grids. A 2D prefix array stores the sum of every submatrix anchored at the top-left corner, and a submatrix sum becomes a four-corner combination over the prefix array instead of a summed loop. There is also a sibling technique called the difference array. It reverses the problem. Instead of answering many range queries on a static array, it applies many range additions to a large array at

O(1)

per update.

When to Use Prefix Sum

These are the problem shapes where prefix sums earn their keep.

The input array is static and you need many range-sum queries. One
O(N)
build pays for itself with
O(1)
queries, which is exactly the profile of Range Sum Query Immutable.
The question asks whether some subarray sums to k, or how many subarrays sum to k. Those reduce to comparing prefix sums, usually by storing what prefix values you have already seen in a hash table.
The numbers can be negative. A sliding window still works when sums only grow, but it breaks once values can go down. Prefix sums handle negative numbers without a special case, because they only ever add.
The input is a matrix and the question is about submatrix sums. A 2D prefix array is the grid version of the same trick.
You have a large collection of range updates with known bounds. Difference arrays process the whole range-update class in
O(1)
time per update.

If the array changes often between queries, prefix sums go stale and you should look for a segment tree or a binary indexed tree instead.

Complexity Analysis

Two numbers define this pattern: the cost to build the prefix array once, and the cost of each query after that.

Operation	Time	Space	Explanation
Build 1D prefix array	O(N)	O(N)	One pass, one running total, N+1 stored values
Single range sum query	O(1)	O(1)	Two array reads, one subtraction
Build 2D prefix array	O(M*N)	O(M*N)	Every cell visited once during the build
2D submatrix query	O(1)	O(1)	Four corner reads, inclusion-exclusion
Prefix sums plus hashmap	O(N)	O(N)	One pass plus a map of prior prefix values

The build is

O(N)

because each element is added into the running total exactly once. The space is

O(N)

because one extra value is stored per input element. The payoff is that the expensive part happens once and the repeated work becomes constant time. If you only need one sum, skip the pattern. The idea exists for the many-queries case, where the one-time build is amortized over hundreds of lookups.

Memorizing complexity tradeoffs is half the battle. The other half is remembering them under pressure. Review this pattern with spaced repetition so the analysis becomes automatic by interview day.

Common Mistakes

These are the bugs that look right in the room and fail on a hidden case.

Off-by-one in the gap index. The query is prefix[right + 1] - prefix[left]. Because prefix[i] is the sum of the first i elements, a range ending at right needs the prefix that includes right, which is prefix[right + 1]. Writing prefix[right] - prefix[left] returns the sum of nums[left..right-1] and drops the last element. To catch this, test a one-element range. The query [2, 2] must return nums[2], and prefix[3] - prefix[2] is the only pair that does.

Building against the wrong source index. In the build loop, prefix[i] draws from nums[i - 1], not nums[i]. Mixing these shifts the whole array by one and the math above breaks completely. Catch it by checking that prefix[1] equals nums[0] on the same input, and that a full-range query equals the whole sum you can compute by hand.

Forgetting the {0: 1} seed in counting problems. When you count subarrays that sum to k with a hashmap, the map must start with the empty prefix set to one. Otherwise every valid subarray that begins at index 0 is never counted, and the answer is short by exactly those cases. The clue that something is wrong is a solution that passes the test with an empty array but fails the first example with a positive answer.

Ignoring overflow. Cumulative sums grow. With large inputs or large values, an int can wrap into negative territory and silently poison every query. In Java use long instead, in C++ use long long, and in Go use int64. If the language you write in has an unbounded integer, no change is needed.

These mistakes are expensive because they look correct until they fail on a hidden test case. Our review decks flag exactly these errors and drill them until they are reflex. Add this pattern to your queue .

Related Patterns

Hash Table . Subarray Sum Equals K and its relatives are prefix sums plus a counting hashmap. The hash table page covers the counting mechanics that do the real work.
Sliding Window . When all values are non-negative, a sliding window answers subarray-sum questions in
O(N)
time and
O(1)
space. When negative numbers appear, sliding windows stop being valid and prefix sums take over.
Kadane’s Algorithm . Kadane finds the single best subarray in
O(N)
time with no extra memory. Prefix sums answer whole batches of range queries. Use the one that matches the shape of the question.

Next Steps

Once the concept is clear, turn it into code you can produce without thinking. The code templates give you the range-query class, the counting variant, and the difference array in six languages. Then work through the practice problems to see the pattern holding up against real interview questions.

Reading about a pattern once is not enough to own it in an interview. Practice this pattern with spaced repetition and turn recognition into recall.