Prefix sum array

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

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] &lt; 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.