Prefix Sum

The Prefix Sum technique is one of the simplest—and most powerful—patterns in algorithm design.
Its purpose is straightforward: precompute cumulative information so that later queries become trivial.

At its core, the idea is:

• Instead of recomputing sums over and over, compute them once in a cumulative array
• and reuse that information in $O(1)$.

What is a Prefix Sum?

Given an array nums, the prefix sum array prefix is defined as:

$$\text{prefix}[i] = \text{nums}[0] + \text{nums}[1] + \ldots + \text{nums}[i]$$

This means each prefix element stores the sum from the start up to index i. Without prefix sums, computing the sum of a range $(L, R)$ requires scanning the array, so $O(n)$ per query. With prefix sums:

$$\text{rangeSum}(L, R) = \text{prefix}[R] - \text{prefix}[L - 1]$$

So, O(1) per query after an initial O(n) preprocessing

This transformation is why prefix sums appear a lot in algorithmic problems involving:

• subarrays
• range queries
• balancing binary arrays
• tracking running differences
• divisibility conditions (mod k prefix sums)

Generalizing what we saw earlier, we can write a general definition of prefix sum.
Once you compute the cumulative array prefix, any range sum becomes a simple subtraction:

$$\text{rangeSum}(L, R) = \text{prefix}[R] - \text{prefix}[L - 1]$$

This works because $\text{prefix}[R]$ contains the sum from the start up to $R$,
while $\text{prefix}[L - 1]$ contains the sum up to just before the range begins.
Subtracting the two removes everything outside the interval and leaves only the sum of the subarray $L...R$.

There is one small edge case: when the range starts at index 0.
In that situation, there's nothing before the range, so the formula simplifies to:

$$\text{rangeSum}(0, R) = \text{prefix}[R]$$

This compact idea, “a range sum is just the difference of two prefix sums”, is the foundation of all prefix-sum techniques.

Patterns

Below are some common patterns that build upon the basic prefix sum idea.

Standard Prefix Sum

The most fundamental version of the technique. It leverages the standard definition of prefix sums and code it. You precompute an auxiliary array prefix[] where each entry contains the cumulative sum from the start of the array up to index i.

Find subarrays with target sum k

When the goal is to find subarrays with a specific target sum, the standard prefix array isn't enough. We need to know how many times a certain prefix sum has appeared before.
The idea behind this the following one. If

$$\text{prefix}[j] - \text{prefix}[i] = k$$

then the subarray $(i+1 \ldots j)$ sums to $k$. This means:

$$\text{prefix}[i] = \text{prefix}[j] - k$$

So for each j, we only need to check whether $\text{prefix}[j] - k$ has appeared before.
A hash map (prefix → frequency) lets us do this in O(1).

So during a scan of the array:

• Let currentPrefix be the running sum.
• Check if currentPrefix - k has been seen before.
• Use a hash map to store frequencies of prefix sums.

This unlocks problems like Subarray Sum Equals K.

Subarray divisible by target value k

Some problems ask whether a subarray sum is divisible by k. Key identity:

$$( \text{prefix}[j] - \text{prefix}[i] ) \ \% \ k == 0$$

implies

$$\text{prefix}[j] \% k == \text{prefix}[i] \% k$$

So instead of storing prefix sums themselves, we store:

$$\text{prefix}[i] \% k$$

in a hash map with their frequencies. Every time we encounter a prefix sum whose modulo k has appeared before, it means that the “excess amount” beyond a multiple of k is the same as in a previous prefix. Because both prefixes leave the same remainder when divided by k, the region between them must add up to an exact multiple of k. Therefore, each previous occurrence of that remainder corresponds to a new subarray whose sum is divisible by k.

Balance Tracking (+1 / -1)

Used in problems involving binary arrays or balancing conditions.
Transform the array:

• 0 → -1
• 1 → +1

After this transformation, a balanced subarray (equal number of 0s and 1s) becomes a subarray with sum = 0.
Then the problem becomes "Find the longest subarray whose prefix sums repeat".
Because if:

$$\text{prefix}[j] == \text{prefix}[i]$$

then the subarray $(i+1 ... j)$ sums to 0.

This technique is central in Contiguous Array.

Time & Space Complexity

Below you can find a summary table of time and space complexities for each pattern discussed.

Exercises