Prefix Sums Explained: Range Sums and Subarray Counts

By Hourly DSA · September 28, 2026 · 4 min read

A prefix sum stores the total before each array position, letting you find a range's sum by subtracting two totals. Build the prefix array once in O(n) time, then answer each range-sum query in O(1) time, assuming fixed-cost arithmetic.

This is useful when many questions refer to the same unchanged array. It also leads to a different technique for counting subarrays with a target sum, including arrays with negative numbers.

Define the prefix array before using the formula

Use zero-based indices and let prefix[i] mean the sum of the first i values. That definition gives prefix[0] = 0, because the first zero values have sum zero.

For this array:

values = [3, -2, 5, 1]
prefix = [0, 3, 1, 6, 7]

The prefix array has one more entry than the input. prefix[3] is 6 because the first three values sum to 3 - 2 + 5.

For a range that includes index left and excludes index right, the formula is:

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

The range [1, 3) contains -2 and 5. Its sum is prefix[3] - prefix[1] = 6 - 3 = 3.

The subtraction removes everything before the range from the total up to its end. The USACO Guide's prefix-sum lesson develops the same preprocessing approach for range queries.

Why the initial zero prevents special cases

A range starting at index zero uses prefix[right] - prefix[0], which works without a separate branch. An empty range uses the same boundary twice, giving zero.

If a problem instead supplies inclusive endpoints, convert them carefully. The sum from index left through index right is prefix[right + 1] - prefix[left] with our definition.

Try the last two elements of the example. Inclusive indices 2 through 3 give prefix[4] - prefix[2] = 7 - 1 = 6. Writing prefix[3] - prefix[2] would omit the final value.

The formula follows from the definition. Mixing a different prefix convention with this formula is a common source of boundary errors.

Count subarrays whose sum equals a target

Suppose you want the number of nonempty contiguous subarrays with sum 3:

[2, -1, 2, 1]

At a current prefix total called total, a subarray ending here has sum 3 whenever an earlier prefix equals total - 3.

Keep a frequency map of earlier prefix totals. Start with {0: 1} to represent the boundary before the first element.

Value read	Current total	Earlier total needed	New matches
2	2	-1	0
-1	1	-2	0
2	3	0	1
1	4	1	1

The two matching subarrays are [2, -1, 2] and [2, 1].

At each step, add the frequency of total - target to the answer, then record the current total. Checking first ensures that a zero target does not count an empty subarray at the current boundary.

Why a set is not enough for counting

Repeated prefix totals correspond to different possible starting boundaries. For [0, 0] and target zero, there are three nonempty subarrays: the first zero, the second zero, and both together.

After the first value, the map records two occurrences of prefix zero: the initial boundary and the boundary after that value. The second value therefore adds two matches.

A set would remember that zero exists but lose how many times it appeared. This is a useful application of the distinction between a hash map and a hash set.

The counting method takes expected O(n) time and O(n) extra space under the usual constant-cost hashing and arithmetic assumptions. You can maintain a running total without storing a separate prefix array.

When should you use a different approach?

For a single range query, adding its elements directly may be all you need. Prefix preprocessing pays off when you reuse the totals.

For frequent changes to array values, a plain prefix array becomes expensive to maintain: changing an early value affects many later totals. That is a different problem from querying a fixed array.

For a fixed-size moving range, a running sliding window may need less storage. For target-sum counting with negative values, prefix differences still work because the subtraction identity does not require totals to increase.

Check your understanding

For [4, -3, 2], the prefix array is [0, 4, 1, 3]. What is the sum from index 1 through index 2, inclusive?

-1, calculated as prefix[3] - prefix[1] = 3 - 4.

Use Hourly DSA for short reasoning practice, then test a boundary change like this one. Being able to explain which prefix to subtract is more useful than recalling a formula without its indexing convention.