Imagine you are given an array and asked to calculate the sum of elements between two indices. Easy enough, you loop through and add them up. But what if you need to answer thousands of such queries on the same array?

Suddenly, that simple loop becomes a bottleneck.

This is where prefix sum comes in. It is one of the most powerful preprocessing techniques in algorithm design, transforming range sum queries from O(n) to O(1).

What is Prefix Sum?

A prefix sum (also called cumulative sum or running total) is a technique where we precompute the sum of all elements from the beginning of an array up to each index.

This preprocessing allows us to answer range sum queries in constant time.

Given an array nums of length n:

In other words, prefix[i] stores the sum of all elements from index 0 to index i.

If the input array is:

The prefix sum array will look like this:

The Key Insight: Range Sums in O(1)

Here is the magic. Once we have the prefix sum array, we can find the sum of any range [left, right] using a simple formula:

sum(left, right) = prefix[right] - prefix[left - 1]

Why does this work? Think about it:

For our example array [2, 4, 1, 3, 5]:

Edge case: When left = 0, there is no prefix[left - 1]. In this case, sum(0, right) = prefix[right].

When to Use Prefix Sum

Prefix sum is the right tool when you see these patterns:

1. Multiple range sum queries on a static array

If the array does not change and you need to answer many range sum queries, preprocessing with prefix sum is almost always the right approach.

2. Counting subarrays with a specific sum

Problems like "find subarrays that sum to k" become tractable with prefix sums combined with a hash map.

3. Finding equilibrium points or balance conditions

When you need to compare sums of left and right portions of an array.

4. 2D grid problems involving rectangular sums

Prefix sums extend naturally to 2D for calculating sums of any rectangular region.

The Prefix Sum Template

Every prefix sum solution follows a similar structure. Let us establish a template.

Building the Prefix Sum Array

Querying a Range Sum

Alternative: Using prefix[0] = 0 Convention

Many implementations use a prefix array of size n + 1, where prefix[0] = 0. This eliminates the edge case for left = 0:

In this convention:

Both conventions are valid. Choose whichever feels more natural, but be consistent.

Prefix Sum + HashMap: A Powerful Combination

Many problems combine prefix sums with a hash map to achieve O(n) solutions for finding subarrays with specific properties.

The key insight is: if prefix[j] - prefix[i] = k, then the subarray from index i+1 to j has sum k.

Rearranging: prefix[i] = prefix[j] - k

So as we compute prefix sums, we can use a hash map to look up whether we have seen a prefix sum that would complete a valid subarray.

This pattern appears in:

We will explore these in detail in the following chapters.

Extending to 2D: Matrix Prefix Sums

Prefix sums extend naturally to 2D grids. For a matrix, we precompute sums of all rectangles from (0,0) to (i,j).

To find the sum of any rectangle from (r1, c1) to (r2, c2):

This achieves O(mn) preprocessing and O(1) per query, the same trade-off as 1D.