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