# This content is archived!

For the 2018-2019 school year, we have switched to using the WLMOJ judge for all MCPT related content. This is an archive of our old website and will not be updated.

# 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.

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.

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.