Calculating the sum of elements between two indices in an array is a simple loop. But when you need to answer thousands of such queries on the same array, that loop becomes a bottleneck.

This is where prefix sum comes in. It is a preprocessing technique that transforms range sum queries from O(n) to O(1).

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:

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]

This works because:

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].

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.

Every prefix sum solution follows a similar structure.

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. Pick one and use it consistently.

In Java/C++/C# with int arrays, sums of large arrays can overflow int. Use long for the prefix array when total sums could exceed ~2 billion.

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

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.

The HashMap pattern uses the n+1-indexed convention where prefix[0] = 0 represents the empty prefix. This is what makes the seed {0: 1} represent the empty-prefix base case.

The map must be initialized with {0: 1} before iteration. This represents the empty prefix and is what makes subarrays starting at index 0 count correctly.

This pattern appears in:

We will explore these in detail in the following chapters.

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.

Visualizing the 2D Formula

The 2D range sum formula uses inclusion-exclusion across four overlapping rectangles. We start with the full rectangle from (0,0) to (r2, c2), subtract the strip above our region, subtract the strip to the left, then add back the top-left corner that got subtracted twice.

rangeSum(r1, c1, r2, c2) = prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] + prefix[r1-1][c1-1]

Prefix sum handles many range sum queries on a static array. Difference array handles the dual problem: many range updates followed by a single read of the final array.

The problem: given an array A of length n and m operations of the form "add v to every element in A[l..r]", produce the final array. The naive approach applies each update in O(n) for a total of O(m * n), which is too slow when both m and n are large.

The Difference Array Trick

Define a difference array D where D[i] = A[i] - A[i-1], with D[0] = A[0]. Each element of D records the change from the previous element of A.

The trick is that any range update on A becomes a two-point update on D. The operation "add v to A[l..r]" becomes:

This works because adding v to A[l..r] increases the jump at index l by v (so D[l] += v) and decreases the jump at index r + 1 by v (so D[r+1] -= v). All differences inside the range stay the same.

Each update is now O(1). After applying all m updates, we recover the final array by taking the prefix sum of D:

A[i] = D[0] + D[1] + ... + D[i]

Total complexity drops to O(m + n).

Walked Example

Start with A = [0, 0, 0, 0, 0] and apply two updates:

After Update 1, diff becomes [3, 0, 0, -3, 0, 0]. After Update 2, diff becomes [3, 2, 0, -3, 0, -2] (length n + 1 = 6).

Now take the prefix sum of diff to recover A:

Final array: A = [3, 5, 5, 2, 2].

LeetCode Problems

The difference array is the canonical solution for:

Recognize the pattern by looking for many range updates with a single final read, or for checking whether some capacity constraint is violated at any index after all updates.

Prefix sum generalizes to any associative operation that has an inverse. Sum uses subtraction as its inverse. XOR is its own inverse, so prefix XOR works the same way.

Define prefixXor[i] = nums[0] ^ nums[1] ^ ... ^ nums[i]. The XOR of any range nums[l] ^ ... ^ nums[r] equals prefixXor[r] ^ prefixXor[l - 1]. Since a ^ a = 0, XOR-ing the two prefixes cancels everything outside the range.

The same HashMap pattern used for "Subarray Sum Equals K" works for "Number of Subarrays with XOR Equal to K". Replace the running sum with a running XOR and the subtraction currSum - k with currXor ^ k.

Prefix min, prefix max, and prefix product also exist but with caveats. Prefix min and prefix max do not support arbitrary range queries because min and max have no inverse. prefixMin[i] only answers "min from 0 to i", not "min from l to r" (for that, use a sparse table or segment tree). Prefix product supports range product queries with division, but breaks when the range contains a zero and needs care with negatives.