Introduction

Given an array $a$ of $N$ integers, answer $Q$ queries: the sum of all the elements in the range $[\text{start}, j]$

To solve this problem, we could sum up the given range for each query, but that would be worst case $\mathcal{O}(N)$ per query. If there are many queries, the program will be extremely slow. The fact that the array doesn’t change throughout the queries tells us that we must use preprocessing: prefix sum array!

There are $N^2$ unique ranges in an array. Creating a $N^2$ sizes array to hold the sums of each possible range would be excessive. The prefix sum array only uses an $N$ sized array.

Like in the name, the array holds the sum of all elements before the given index. ps[i] of the prefix sum array contains the sum of the array indices $[0, i)$.

Example

Given the following array:

The prefix sum array will look like:

ps[4] has a value of 6. It corresponds to the sum of the range $[0, 3]$.

Say we want only the range $[2, 3]$. We have 2 extra elements in the sum, so we must subtract them.

The subtracted region is the first two elements: ps[2].

It adds up. We want the sum of the range $[2, 3]$: -2 + 1 = -1 = ps[4] - ps[2] = 6 - 7.

In short, the sum of the range $[\text{start}, \text{end}]$ is ps[end + 1] - ps[start].

You may have noticed that the prefix sum array has an extra element, the 0 at the start of the array. This makes it more convenient to handle queries asking for the sum of the range $[0, \text{end}]$.

Implementation

Constructing a prefix sum array is relatively easy, as shown in the code snippet below where ps is the new prefix sum array, a is the original array, and N is the original array size.

int[] ps = new int[N + 1]; // An extra element, the 0 at the start of the prefix sum array

for (int n = 1; n <= N; n++) {
	ps[n] = ps[n - 1] + a[n - 1];
}

Finding the sum between any two indexes of a given array can be implemented as below. This method assumes that the constraints 0 < l ≤ r < N are held.

public static int sum(int l, int r) { // Left and right ends of the range
	return ps[r + 1] - ps[l];
}

Notice that when querying for the range $[0, i]$, ps[l] = 0 due to the extra element appended to the start. Without this element (or an if statement to handle the special case where l == 0), the program would crash due to an index out of bounds (-1).

Time Complexity

Construction: $\mathcal{O}(N)$, where $N$ is the size of the original array.

Sum Query: $\mathcal{O}(1)$

Space Complexity

$\mathcal{O}(N)$, where $N$ is the size of the original array.

The prefix sum array is a data structure which allows fast calculation of the sum of a given range of numbers. With the prefix sum array, the total runtime to solve the given problem is now $O(N + Q)$, which is a large improvement over the naive solution.

Practice

DMOPC ‘14 Contest 2 P4: Deforestation
GFSSOC ‘14 Spring P4: Marathon
MWC ‘15 Contest 7 P2: Thief in the Night