Prefix sums: a range sum as the difference of two numbers

← Back to the section

A sliding window works beautifully when there is one range and it crawls along. But what if the ranges are arbitrary and there are many of them: "how much did we earn from the third day to the tenth", then "from the first to the fifth", and so on a thousand times? Adding it up from scratch every time costs O(N) per query. The prefix sums technique answers such a query in O(1) after a single preparation pass.

The idea: a running total

Let us build an array where position i holds the sum of all elements before i. That is a running total — the same thing as revenue accumulated since the start of the year.

Then a range sum is simply the difference of two accumulated totals: "how much had piled up by the end of the range" minus "how much had piled up by its start". Everything before the start of the range cancels out and no longer gets in the way.

live example

import java.util.Arrays;

public class Revenue {
    private final long[] prefix;

    Revenue(int[] daily) {
        prefix = new long[daily.length + 1];
        for (int i = 0; i < daily.length; i++) prefix[i + 1] = prefix[i] + daily[i];
    }

    long range(int l, int r) {
        return prefix[r + 1] - prefix[l];
    }

    public static void main(String[] args) {
        Revenue revenue = new Revenue(new int[]{2, 5, 1, 4, 3, 7, 2, 6});
        System.out.println("prefix: " + Arrays.toString(revenue.prefix));
        System.out.println("days 1..3: " + revenue.range(1, 3));
        System.out.println("days 4..7: " + revenue.range(4, 7));
    }
}

Preparation is O(N), done once. Every query is O(1). With a thousand queries over a million days that is the difference between "instantly" and "half a minute".

Why the array is one cell longer

Notice that prefix is longer than the original array and that prefix[0] is zero. That is not an accident but a way to get rid of a special case.

If the prefixes had the same length as the data (prefix[i] = the sum up to and including i), the formula would be prefix[r] - prefix[l - 1], and for l == 0 we would reach for prefix[-1]. A check would be needed on every single query. The extra zero at the front is the "empty sum", and it makes the formula uniform for every range.

This trick — add a dummy element to remove a special case — shows up often; in linked lists the dummy head plays exactly the same role.

Not only sums

The technique works with any operation that has an inverse.

Counting by a flag. To answer "how many cancelled orders are there between days l and r" quickly, build the prefixes not over revenue but over ones and zeros: one if the order was cancelled. A range sum turns into a count.

Averages. A range sum divided by the length of the range is O(1) as well.

Minimum and maximum, however, are out of reach: they have no inverse operation, and you cannot subtract the excess out of "the minimum over a prefix". Such queries need other structures — heaps or segment trees, for example.

The reverse problem: many updates, one query

Sometimes it is the other way round: the ranges are never read, a number is added to all of them in bulk, and only at the very end is the resulting array needed. "Add one to every day of the promotion" — and there are thousands of such promotions.

The mirror trick helps here: the difference array. Instead of touching the whole range, mark two places only: add at the start of the range, subtract right after its end.

live example

import java.util.Arrays;

public class Promotions {
    public static void main(String[] args) {
        int days = 8;
        int[][] ranges = {{0, 2}, {1, 5}, {4, 7}};
        int[] diff = new int[days + 1];
        for (int[] r : ranges) {
            diff[r[0]] += 1;
            diff[r[1] + 1] -= 1;
        }
        int[] result = new int[days];
        int running = 0;
        for (int i = 0; i < days; i++) {
            running += diff[i];
            result[i] = running;
        }
        System.out.println("promotions per day: " + Arrays.toString(result));
    }
}

Every update is O(1) instead of O(length of the range), and at the end a single pass with a running total restores the answer. In essence these are prefix sums applied backwards.

Two dimensions

If the data is a table (sales by day and by warehouse, say), the same technique extends to rectangles. prefix[i][j] holds the sum of the whole rectangle from the top left corner down to cell (i, j).

The sum of an arbitrary rectangle comes out of four numbers: take the big rectangle, subtract the strip on the left and the strip on top — the corner has now been subtracted twice, so it is added back. Preparation is O(N·M), any query is O(1).

What it costs

The technique is not free, and three things are worth remembering.

Memory. An extra array the size of the original one is needed. For the two-dimensional case, a whole extra table.

Immutable data only. If an element changes, every prefix after it becomes wrong and has to be recomputed in O(N). Prefix sums are good where the data is written once and read many times.

Overflow. Sums grow, and int runs out sooner than it seems: a million days at a couple of thousand each gives two billion — right up against the int limit (2 147 483 647), and slightly larger numbers are enough to make the sum negative. Silently, too: Java does not report overflow, it simply keeps counting with a corrupted value. That is exactly why the prefixes in the examples above are declared as long.

How this is done in Java

There is no ready-made "range sum" structure in the standard library — the prefix array is built by hand anyway. What the library does give is a way to compute it, and a choice of what to keep it in.

Keep it in a primitive long[], and not out of spite. ArrayList<Long> holds references to Long objects rather than numbers: every value is a separate object on the heap, several times more memory goes to waste, and walking the list jumps around memory instead of going straight through it. Formally the complexity is the same; in practice the gap is several-fold — and a running total is precisely one long sequential pass.

The running total itself the library can compute — that is Arrays.parallelPrefix:

live example

import java.util.Arrays;

public class ParallelPrefix {
    public static void main(String[] args) {
        long[] daily = {2, 5, 1, 4};
        System.out.println("before: " + Arrays.toString(daily));
        Arrays.parallelPrefix(daily, Long::sum);
        System.out.println("after:  " + Arrays.toString(daily));
    }
}

The second argument is the operation — it does not have to be addition, but it does have to be associative: the method cuts the array into chunks and processes them independently, so the result must not depend on how the brackets are arranged.

There is one gotcha here, an annoying one, and the example shows it: the method works in place. After the call the original numbers are gone — the array holds the accumulated total only, and the daily revenue cannot be recovered. It does not add the leading zero either, and without it the formula needs a special case for a range starting at position zero. So the prefix array is still prepared by hand: one cell longer, with a zero at the front and a copy of the data inside. And "parallel" in the name is not a promise of a win: splitting the work across threads pays off on hundreds of thousands of elements, while on a short array a plain one-line loop is faster.

In short

• Prefix sums are a precomputed running total; the sum of any range becomes the difference of two numbers.
• Preparation is O(N) once, every query is O(1) — the technique pays off when there are many queries.
• The prefix array is made one cell longer with a zero at the front: that way the formula also works for a range starting at position zero.
• It works for sums and for counting by a flag; it does not work for minimum and maximum — they have no inverse operation.
• The mirror variant is the difference array: bulk additions over ranges at O(1) each, with the result assembled by one pass at the end.
• The costs: extra memory, the data has to be immutable, and sums overflow int easily.

What to read next

• Two pointers and the sliding window — the neighbouring range technique, for when there is one range and it crawls.
• Monotonic stack — how the maximum questions are answered, the ones prefix sums cannot reach.
• Dynamic programming — the same "compute once and remember" principle for problems with a harder transition.
• Arrays, binary search and big O — where the O(1) and O(N) used all over this article come from.