Prefix Sum

Prefix sum stores cumulative totals so range sums can be answered quickly.

It is one of the simplest preprocessing techniques for array and sequence problems.

Core Idea

The prefix sum at position i stores the sum of values before or up to that position. A range sum can then be computed by subtracting two prefix sums instead of scanning the range.

This changes repeated range-sum queries from O(length of range) to O(1) after preprocessing.

Function Contracts

build_prefix(values) expects numeric values and returns a prefix list with one extra leading zero.

range_sum(prefix, left, right) expects prefix to come from build_prefix and left and right to be valid inclusive indexes in the original array. It returns the sum from left through right.

Python Example

def build_prefix(values):
    prefix = [0]
    for value in values:
        prefix.append(prefix[-1] + value)
    return prefix
 
 
def range_sum(prefix, left, right):
    return prefix[right + 1] - prefix[left]

The extra leading 0 makes the subtraction formula simpler.

Step-by-Step Example

For:

values = [3, 1, 4, 2]

the prefix array with a leading zero is:

index:   0  1  2  3  4
prefix:  0  3  4  8 10

The sum from index 1 to index 3 is:

prefix[4] - prefix[1] = 10 - 3 = 7

which matches 1 + 4 + 2.

Why It Works

prefix[right + 1] contains the sum of everything before and through right. prefix[left] contains the sum before left. Subtracting removes the part before the range and leaves only the range.

Complexity

Building the prefix array is O(n) time and O(n) space. Each range-sum query is O(1).

Common Confusions

Be clear about whether a prefix array stores sums before index i or through index i. Mixing conventions creates off-by-one errors.

Prefix sums help with range sums on mostly fixed data. If many updates happen, a different structure may be needed.

Another common mistake is forgetting the leading zero and then using the wrong formula for ranges that start at index 0.

When To Use It

Use prefix sums when many queries ask for sums over contiguous ranges, or when a problem can be transformed into differences between cumulative totals.

Do not use a static prefix sum alone when the array changes after each query. Updates would require rebuilding or a different structure.

The Main Point

Prefix sums turn repeated static range sums into subtraction between cumulative totals.