Prefix sums

Eight values, and under them their running totals. Watch one subtraction give the sum of four values, then watch what one change costs.

⋯8void build(void)9{10    prefix[0] = 0;11    for (int i = 0; i < N; i++)12        prefix[i + 1] = prefix[i] + a[i];13}14 15int range_sum(int i, int j)16{17    return prefix[j + 1] - prefix[i];18}19 20int update(int i, int value)21{22    int delta = value - a[i];23    a[i] = value;24    int touched = 0;25    for (int k = i + 1; k <= N; k++) {26        prefix[k] += delta;27        touched++;28    }29    return touched;30}⋯40int main(void)41{42    build();43    print_prefix();44    int s1 = range_sum(2, 5);45    printf("sum a[2..5] = %d\n", s1);46    int t = update(3, 5);47    print_prefix();48    int s2 = range_sum(2, 5);49    printf("after a[3] = 5: %d totals changed, sum a[2..5] = %d\n", t, s2);50    return 0;51}

Running totals

The prefix sum prefix[k] is the sum of the first k values of the array, a[0] to a[k − 1]. There is one more total than there are values: prefix[0] is the sum of no values, 0, and prefix[8] is the sum of all eight.

The sum of a range is a difference of two totals. prefix[6] adds a[0] to a[5]; prefix[2] adds a[0] and a[1]. Take the second from the first and a[2] to a[5] are left: 27 − 7 = 20, which is 7 + 1 + 4 + 8.

The code and its cost

Building the totals

static int a[N] = { 5, 2, 7, 1, 4, 8, 3, 6 };
static int prefix[N + 1];

void build(void)
{
    prefix[0] = 0;
    for (int i = 0; i < N; i++)
        prefix[i + 1] = prefix[i] + a[i];
}

Each total is the one before plus one value, so building takes one addition per value: n steps, O(n), for an array of n values. Both arrays are static, outside any function, so prefix starts as zeros before build writes it.

A range sum

int range_sum(int i, int j)
{
    return prefix[j + 1] - prefix[i];
}

The range here includes both ends, a[i] to a[j]. prefix[j + 1] is the sum up to and including a[j]; prefix[i] is the sum of everything before a[i]. One subtraction, O(1), however long the range.

A common slip is prefix[j] − prefix[i]. That leaves out a[j]: for a[2..5] it gives 19 − 7 = 12, not 20. The leading 0 is what makes the formula work for every range, including one that starts at a[0]: sum a[0..j] is prefix[j + 1] − prefix[0], with no special case.

An update

int update(int i, int value)
{
    int delta = value - a[i];
    a[i] = value;
    int touched = 0;
    for (int k = i + 1; k <= N; k++) {
        prefix[k] += delta;
        touched++;
    }
    return touched;
}

Every total that includes a[i] must change by the same amount, delta. Those are prefix[i + 1] to prefix[n], n − i totals. Setting a[3] from 1 to 5 adds 4 to five totals, prefix[4] to prefix[8]; an update to a[0] would change all eight. So an update costs O(n), and a long array that changes often makes prefix sums slow. Segment trees and Fenwick trees make both a range sum and an update take O(log n).

prefix: 0 5 7 14 15 19 27 30 36
sum a[2..5] = 20
prefix: 0 5 7 14 19 23 31 34 40
after a[3] = 5: 5 totals changed, sum a[2..5] = 24

Moving averages

The average of w values starting at a[k] is (prefix[k + w] − prefix[k]) / w: one subtraction and one division per sample, whatever w is. A moving average built this way is the moving-average filter of Smoothing filters, at a cost that does not grow with the window.

Two dimensions

For a grid of values, let P[r][c] hold the sum of the rectangle of rows 0 to r − 1 and columns 0 to c − 1, with a row and a column of zeros at the top and left as prefix[0] is. The sum of the rectangle of rows r₁ to r₂ − 1 and columns c₁ to c₂ − 1 is then P[r₂][c₂] − P[r₁][c₂] − P[r₂][c₁] + P[r₁][c₁]: the big rectangle, minus the strip above and the strip to the left, plus the corner both took away. Four lookups for any rectangle.

Running it yourself

gcc -std=c11 -Wall -Wextra -pedantic prefix.c -o prefix
./prefix

Worked example

Two ranges. sum a[0..7] = prefix[8] − prefix[0] = 36 − 0 = 36. sum a[4..4] = prefix[5] − prefix[4] = 19 − 15 = 4, the single value a[4].

Moving sums of 3, on the original array: prefix[3] − prefix[0] = 14, then prefix[4] − prefix[1] = 10, then 12, 13, 15 and 17. Six windows of three values, six subtractions.

Which two cells give sum a[1..3]? prefix[4] − prefix[1] = 15 − 5 = 10, which is 2 + 7 + 1.

A million values and a million queries. With prefix sums, a million additions to build and a million subtractions to answer. Summing each range afresh could take up to a million additions a query, up to 10¹² in all.

Where it’s used

Signal processing. Moving averages of samples, at a fixed cost per sample whatever the window.

Image filters. A summed-area table, the two-dimensional prefix sums, gives the sum of any rectangle of pixels in four lookups, for fast box blurs and feature detection.

Databases. Range totals over data that rarely changes, such as sales by day, are answered from stored running totals.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.