Data structures and algorithms 0/7

DSA, Arrays and searching

What is a prefix sum?

Also called prefix sums, cumulative sum, running total

481 words · 3 min read

A prefix sum is the sum of the first few values of an array: the first one, the first two, the first three, and so on. The sum of any range is one prefix sum minus a shorter one, so if we compute every prefix sum once and store them, each range sum takes a single subtraction, for a range of 2 values or of 200,000.

Build the prefix array and subtract two entries

We store the prefix sums in a second array called prefix, where prefix[i] is the sum of the first i values of nums. For [4, 2, 7, 1]:

The highlighted entry prefix[3] = 13 is the sum of the three highlighted values, 4+2+74 + 2 + 7.

Four values give five entries, because the array starts with prefix[0] = 0, the sum of no values. Each later entry is the one before it plus one more value, so a single pass over nums fills the array with one addition per value:

prefix[i+1]=prefix[i]+nums[i]\texttt{prefix}[i + 1] = \texttt{prefix}[i] + \texttt{nums}[i]

To answer a question, we subtract two entries. prefix[3] = 13 is the sum of positions 0, 1 and 2, and prefix[1] = 4 is position 0 alone, so 13−4=913 - 4 = 9 is the sum of positions 1 and 2. In general, prefix[right] - prefix[left] is the sum of the first right values without the first left values, which leaves the values at positions left through right - 1.

Each value is drawn with its own length, so a prefix sum is a distance from the start. Removing the shorter prefix from the longer one leaves exactly the range.

In the figure, the entries of prefix sit on the boundaries between values: prefix[0] before the first value and prefix[4] after the last. A range is the stretch between two boundaries, so we name it by those two numbers and write it [left, right). The square bracket says that position left is included, and the round bracket says that the range stops just before position right. This is a half-open range, and the range we just summed is [1, 3).

When prefix sums work

Prefix sums need two things. First, the array must stay fixed between questions. Changing one value changes every prefix entry after it, which can be all nn of them. When changes and questions alternate, a Fenwick tree handles each one in O(log⁡n)O(\log n) steps.

Second, the operation must be one you can undo, because the answer starts from a longer prefix and takes the shorter prefix back out. Subtraction undoes addition, so sums work. Counts work too, because a count is a sum of 1s: mark each value with 1 if it passes the test and 0 if it does not, and take prefix sums of the marks. To count even values in [4, 2, 7, 1], the marks are [1, 1, 0, 0] and their prefix sums are [0, 1, 2, 2, 2]. The range [1, 4) holds 2−1=12 - 1 = 1 even value, the 2.

Prefix sums Answer any range sum with one subtraction of prefix sums, apply range additions with two writes each, and count subarrays by their prefix sums. Read the full lesson