Prefix sum

Also called: Running sum, Cumulative sum

An array of running totals, where position i holds the sum of the first i numbers, so any range sum is one subtraction.

Definition

Building the prefix array takes one pass. After that, the sum of the numbers from index l to r is prefix[r + 1] minus prefix[l], in constant time. Starting the array with a 0 removes special cases for ranges that begin at index 0. Together with a hash map of earlier prefix sums, the idea also counts subarrays with a given sum, even when numbers can be negative.

In practice

For [3, 1, 4, 1, 5] the prefix array is [0, 3, 4, 8, 9, 14], and the sum of indexes 1 to 3 is 9 - 3 = 6.

Learn it in context

Lessons that use this term.

Arrays and stringsCoding

Related terms

Hash mapA key-value collection that finds a value by its key in constant time on average.
Sliding windowA technique that keeps a running result for a contiguous range and updates it as the range moves, instead of recomputing every subarray.