### Prefix sum array

Reading time: 20 minutes | Coding time: 6 minutes

**Prefix Sum array** is a data structure design which helps us to answer several queries such as sum in a given range in **constant time** which would otherwise take linear time. It requires a linear time preprocessing and is widely used due to its simplicity and effectiveness.

Given an array, its prefix array is an array of same size such that i^{th} element of prefix array is the sum of all elements of given array till it's i^{th} element that is **prefix_array[i] = array[0] + arrat[1] + ... + array[i]**

It is used for applications like:

- Find sum of all elements in a given range
- Find product of all elements in a given range
- Find maximum subarray sum
- Find maximum subarray sum modulo m
- Maximum subarray such that sum is less than some number

and many others

**Prefix array** is majorly used to find **sum of elements in an interval** or in Kadane's algorithm. These problems can be answered in **linear time**. Prefix sum array, however, can only be used if array elements do not change. Otherwise prefix array will have to be built with each change.

### Pseudocode

#### Building the prefix array

```
function build(array[]):
n = array.length
prefix_array = {0, 0 ...n times... 0}
prefix_array[0] = array[0]
for i = 1 to n:
prefix_array[i] = ar[i] + prefix_array[i - 1]
return prefix_array
```

#### To find sum of elements in an interval

```
function rangeSum(L, R):
if L == 0:
return prefix_array[R]
else:
return (prefix_array[R] - prefix_array[L - 1])
```

#### To find subarray with maximum sum

This algorithm is also called Kadane's algorithm That involves a modification in building algorithm. The algorithm below returns the max possible contiguous subarray sum.

```
function build(array[]):
n = array.length
prefix_array = {0, 0 ...n times... 0}
prefix_array[0] = array[0]
for i = 1 to n:
prefix_array[i] = ar[i] + prefix_array[i - 1]
# modification here
if prefix_array[i] < 0:
prefix_array[i] = 0
return prefix_array[n - 1]
```

### Complexity

The time and space complexity of Prefix Sum array are as follows:

**Space complexity** : **O(n)**

Worst case time complexities

**Build**:**O(n)****Range sum query**:**O(1)**

Where n is the length of array.

### Implementations

Code in **C++ 11**:

```
/*
* Prefix sum tree to find sum of a given range
*/
#include <iostream>
#include <vector>
std::vector<int> build(const std::vector<int> &array){
int n = array.size();
std::vector<int> prefix_array(n, 0);
prefix_array[0] = array[0];
for(int i = 1; i < n; ++i)
prefix_array[i] = array[i] + prefix_array[i - 1];
return prefix_array;
}
int rangeSum(const std::vector<int> &prefix_array, int L, int R){
if(L == 0)
return prefix_array[R];
else
return (prefix_array[R] - prefix_array[L - 1]);
}
int main() {
std::vector<int> ar = {1, 2, 3, 4, 5};
std::cout << "Array is\n";
for(int i = 0; i < 5; ++i)
std::cout << ar[i] << ' ';
std::cout << '\n';
std::vector<int> prefix_array = build(ar);
std::cout << "Sum of elements in interval [0, 3] = "
<< rangeSum(prefix_array, 0, 3) << '\n';
return 0;
}
```

### Applications

The applications of Prefix Sum array are:

- Used to answer range-sum-query, range-xor-query etc.
- Used to find subarray with max sum.
- Used to find subarray with sum closest to given number.
- Used to find equal length and equal sum subarrays of 2 arrays.

### References/ Further reading

- Prefix sum tree can be extended to 2D to answer submatrix sum query.