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

# Practice

DMOPC ‘14 Contest 2 P4: Deforestation

GFSSOC ‘14 Spring P4: Marathon

MWC ‘15 Contest 7 P2: Thief in the Night