Prefix Sum

Given an array arr of size n, the prefix sum is another array (say prefixSum) of same size such that for each index 0 <= i < n prefixSum[i] denotes a[0] + a[1] .... + a[i].

Scope

This article tells about the prefix sum.

In this article we will learn different approaches to find the prefix sum.

In this article we will learn How to Calculate the Sum from l to r using Prefix Sums.

In this article we will learn Use Cases and Application of Prefix Sum.

Takeaways

While traversing the array, update the element by adding it with its previous element.

Problem Statement

Given an integer array arr of size n, return an array of the same size where the value stored at the $i^{th}$ index of this newly formed array denotes the sum of the subarray of arr that starts from the $0^{th}$ index and ends at the $i^{th}$ index.

Example

Input : a[] = {3, 2, 1, 5, 4}
Output : prefixSum[] = {3, 5, 6, 11, 15}
Explanation :
The below given table shows, how the prefixSum array can be created using the given array.

Solution

Brute Force Approach

One of the brute force approach to construct the prefixSum array is, for each index i compute the the value of a[0] + a[1] + ... + a[i], and store the result in prefixSum[i].

The pseudocode of this approach is –

// Function to compute the prefix sum 
// of the array passed as argument.
function computePrefixSum (a, n):
	// Declare 'prefixSum' array of same size.
	prefixSum = []
	
	// Iterate from i = 0 To i = n - 1
	For (i = 0 To i = n - 1):
		// Declare a variable sum, and initialize
		// its value to 0.
		sum = 0
		
		// Iterate from j = 0 To j = i
		For (j = 0 To j = i):
			// Add the value of a[j] to sum
			sum = sum + a[j]
		
		// Store the value of sum in prefixSum[i]
		prefixSum[i] = sum
	
	Return prefixSum
	
end function

So, we are done, we have seen the algorithm and code and now we are good to go. If you are thinking the same, please go through the pseudocode again and try to determine its time complexity.

The time complexity of this approach is $O(n^2)$, which can be easily optimized to $O(n)$ by using the simple trick described in the next section.

Efficient Approach

Intuition

Before discussing the efficient approach, let us first see the simple mathematics required to build intuition toward this approach.
Let’s say we need to find the sum of elements $x_1 + x_2 + … + x_n$ and due to some reason we already calculated the sum of $x_1 + x_2 + … + x_{n-1}$ in the past. Now we have two options –

1. Calculate the sum of all elements again.
2. Or use the associative property of addition $i.e -$
   $\sum_1^n x_i = (\sum_1^{n-1} x_i )+ x_n$

Obviously the latter requires much fewer calculations as we already have the value $\sum_1^{n-1} x_i$ and we just need to add $x_n$ to it to obtain the desired result.

Now, let’s see how we can use this to find the prefix sum efficiently.

Algorithm

It can noticeable that,
$prefixSum[0] = a[0]$ in all cases because it is the first element. And, for all other indices i the prefix sum can be calculated using the formula $prefixSum[i] = prefixSum[i-1] + a[i]$ because while calculating the $prefixSum[i-1]$ we already had calculated $a[0] + a[1] + … +a[i-1]$. Therefore, to calculate the prefixSum[i] i.e. $a[0] + a[1] + … + a[i]$ we just need to add a[i] in $prefixSum[i-1]$.

The steps required in the algorithm is as follows –

• Declare an array prefixSum of size n with all its entries initialized to 0.
• Assign a[0] to prefixSum[0].
• Iterate from i = 0 to i = n - 1 and do the following –
  • Store the value of prefixSum[i-1] in a varaible (say prev).
  • Assign the value prev + a[i] to prefixSum[i].
• Return prefixSum.

Java Implementation

public class Main{

    // Function to print the array.
    static void printArray(int[] a) {
        for (int x : a)
            System.out.print(x + " ");
        System.out.println();
    }

    static int[] findPrefixSum(int[] a, int n) {
        // Defining the prefix Sum array
        int prefixSum[] = new int[n];

        // Assigning a[0] to prefixSum[0]
        prefixSum[0] = a[0];

        // Iterating from i = 1 To i = n - 1
        for (int i = 1; i < n; i++){
            // Finding prefixSum[i-1]
            int prev = prefixSum[i-1];

            // Calculating and assigning the 
            // value of prefixSum[i].
            prefixSum[i] = prev + a[i];
        }

        // Returning the prefixSum array.
        return prefixSum;
    }

    // Main function
    public static void main(String[] args) {
        // Defining the array.
        int a[] = {3, 2, 1, 5, 4};

        // Calling 'findPrefixSum' to get prefixSum array.
        int prefixSum[] = findPrefixSum(a, a.length);

        // Printing the prefixSum array.
        System.out.println("The prefix sum array is -");
        printArray(prefixSum);
    }
}

Output –

The prefix sum array is -
3 5 6 11 15 

C++ Implementation

#include<bits/stdc++.h>
using namespace std;

// Function to print the array.
void printArray(int *a, int n) {
    for (int i = 0; i < n; i++){
        cout << a[i] << " ";
    }
    cout << endl;
}

int *findPrefixSum(int *a, int n) {
    // Defining the prefix Sum array
    int *prefixSum = new int[n];

    // Assigning a[0] to prefixSum[0]
    prefixSum[0] = a[0];

    // Iterating from i = 1 To i = n - 1
    for (int i = 1; i < n; i++){
        // Finding prefixSum[i-1]
        int prev = prefixSum[i-1];

        // Calculating and assigning the 
        // value of prefixSum[i].
        prefixSum[i] = prev + a[i];
    }

    // Returning the prefixSum array.
    return prefixSum;
}

// Main function
int main() {
    // Defining the array.
    int a[] = {3, 2, 1, 5, 4};

    int len = sizeof(a)/sizeof(a[0]);
    // Calling 'findPrefixSum' to get prefixSum array.
    int *prefixSum = findPrefixSum(a, len);

    // Printing the prefixSum array.
    cout << "The prefix sum array is -" << endl;
    printArray(prefixSum, len);

    return 0;
}

Output –

The prefix sum array is -
3 5 6 11 15 

Python Implementation

# Function to print the array.
def printArray(a, n):
    for x in a:
        print(x, end = " ")
    print()


def findPrefixSum(a, n) :
    # Defining the prefix Sum array
    prefixSum = [0]*n

    # Assigning a[0] to prefixSum[0]
    prefixSum[0]= a[0]

    # Iterating from i = 1 To i = n - 1
    for i in range(1, n):
        # Finding prefixSum[i-1]
        prev = prefixSum[i-1]

        # Calculating and assigning the 
        # value of prefixSum[i].
        prefixSum[i] = prev + a[i]
    

    # Returning the prefixSum array.
    return prefixSum


# Driver code

# Defining the array.
a = [3, 2, 1, 5, 4]

length = len(a)
# Calling 'findPrefixSum' to get prefixSum array.
prefixSum = findPrefixSum(a, length)

# Printing the prefixSum array.
print("The prefix sum array is -")
printArray(prefixSum, length)

Output –

The prefix sum array is -
3 5 6 11 15 

Complexity Analysis

Time Complexity – Since, we are traversing the array only once, which requires O(n)O(n) steps. Therefore, the time complexity is O(n)O(n).

Space Complexity – An array of size nn is required to store the answer. Therefore the space complexity is O(n).

How to Calculate the Sum from l to r using Prefix Sums?

Suppose that due to some reasons, we need to compute multiple range sum queries $sum[l, r]$. Where $sum[l, r]$ means sum array elements whose indices are in range $[l, r]$ $i.e.$ a[l] + a[l+1] + ... + a[r].
The brute force method is to find the sum using the for loop, which costs $O(n)$ time per query. While the efficient method uses the prefixSum array to answer each query in constant time. Let’s see how –

Let’s say we have an query $sum[l, r]$, now we know that
$prefixSum[r] = a[0] + a[1] + … + a[r]$ and $prefixSum[l-1] = a[0] + a[1] + … + a[l-1]$
Now, if we calculate
$prefixSum[r] – prefixSum[l – 1]$
i.e. $a[0] + a[1] + … + a[l] + .. + a[r] – (a[0] + a[1] + … + a[l – 1])$, we obtain the required answer i.e. $a[l] + a[l + 1] … + a[r]$

The steps required to find are –

1. Let’s say we have constructed the prefixSum array.
2. For each query range sum query $sum[l, r]$ do the following –
   • If l = 0, simply return prefixSum[r].
   • Otherwise, return prefixSum[r] - prefixSum[l - 1].

Java Implementation

public class Main{

    // Function to find range sum query.
    static int rangeSumQuery(int[] prefixSum, 
                    int l, int r) {
        // If l = 0
        if (l == 0)
            return prefixSum[r];
        
        // Otherwise find and return 
        // prefixSum[r] - prefixSum[l-1].
        return prefixSum[r] - prefixSum[l - 1];
    }

    static int[] findPrefixSum(int[] a, int n) {
        // Defining the prefix Sum array
        int prefixSum[] = new int[n];

        // Assigning a[0] to prefixSum[0]
        prefixSum[0] = a[0];

        // Iterating from i = 1 To i = n - 1
        for (int i = 1; i < n; i++){
            // Finding prefixSum[i-1]
            int prev = prefixSum[i-1];

            // Calculating and assigning the 
            // value of prefixSum[i].
            prefixSum[i] = prev + a[i];
        }

        // Returning the prefixSum array.
        return prefixSum;
    }

    // Main function
    public static void main(String[] args) {
        // Defining the array.
        int a[] = {3, 2, 1, 5, 4};

        // Calling 'findPrefixSum' to get prefixSum array.
        int prefixSum[] = findPrefixSum(a, a.length);

        System.out.println("The sum of range [2, 4] is " + 
                        rangeSumQuery(prefixSum, 2, 4));

        System.out.println("The sum of range [0, 4] is " + 
                        rangeSumQuery(prefixSum, 0, 4));

        System.out.println("The sum of range [1, 3] is " + 
                        rangeSumQuery(prefixSum, 1, 3));
    }

}

Output –

The sum of range [2, 4] is 10
The sum of range [0, 4] is 15
The sum of range [1, 3] is 8

C++ Implementation

#include<bits/stdc++.h>
using namespace std;

// Function to find range sum query.
int rangeSumQuery(int *prefixSum, 
                int l, int r) {
    // If l = 0
    if (l == 0)
        return prefixSum[r];
    
    // Otherwise find and return 
    // prefixSum[r] - prefixSum[l-1].
    return prefixSum[r] - prefixSum[l - 1];
}

int *findPrefixSum(int *a, int n) {
    // Defining the prefix Sum array
    int *prefixSum = new int[n];

    // Assigning a[0] to prefixSum[0]
    prefixSum[0] = a[0];

    // Iterating from i = 1 To i = n - 1
    for (int i = 1; i < n; i++){
        // Finding prefixSum[i-1]
        int prev = prefixSum[i-1];

        // Calculating and assigning the 
        // value of prefixSum[i].
        prefixSum[i] = prev + a[i];
    }

    // Returning the prefixSum array.
    return prefixSum;
}

// Main function
int main() {
    // Defining the array.
    int a[] = {3, 2, 1, 5, 4};

    int len = sizeof(a)/sizeof(a[0]);
    // Calling 'findPrefixSum' to get prefixSum array.
    int *prefixSum = findPrefixSum(a, len);

    cout << "The sum of range [2, 4] is " << 
                rangeSumQuery(prefixSum, 2, 4) << endl;

    cout << "The sum of range [0, 4] is " << 
                rangeSumQuery(prefixSum, 0, 4) << endl;

    cout << "The sum of range [1, 3] is " << 
                rangeSumQuery(prefixSum, 1, 3) << endl;

    return 0;
}

Output –

The sum of range [2, 4] is 10
The sum of range [0, 4] is 15
The sum of range [1, 3] is 8

Python Implementation

# Function to find range sum query.
def rangeSumQuery(prefixSum, l, r):
    # If l = 0
    if (l == 0):
        return prefixSum[r]
    
    # Otherwise find and return 
    # prefixSum[r] - prefixSum[l-1].
    return prefixSum[r] - prefixSum[l - 1]
    
# Function to find the prefix sum
def findPrefixSum(a, n) :
    # Defining the prefix Sum array
    prefixSum = [0]*n

    # Assigning a[0] to prefixSum[0]
    prefixSum[0]= a[0]

    # Iterating from i = 1 To i = n - 1
    for i in range(1, n):
        # Finding prefixSum[i-1]
        prev = prefixSum[i-1]

        # Calculating and assigning the 
        # value of prefixSum[i].
        prefixSum[i] = prev + a[i]
    

    # Returning the prefixSum array.
    return prefixSum


# Driver code

# Defining the array.
a = [3, 2, 1, 5, 4]

length = len(a)
# Calling 'findPrefixSum' to get prefixSum array.
prefixSum = findPrefixSum(a, length)

print ("The sum of range [2, 4] is ", 
        rangeSumQuery(prefixSum, 2, 4))

print ("The sum of range [0, 4] is ", 
        rangeSumQuery(prefixSum, 0, 4))

print ("The sum of range [1, 3] is ", 
        rangeSumQuery(prefixSum, 1, 3))

Output –

The sum of range [2, 4] is 10
The sum of range [0, 4] is 15
The sum of range [1, 3] is 8

Complexity Analysis

Time Complexity – If the size of the array is $n$ and we need to answer $q$ queries, the time complexity is $O(n + q)$. Where $O(n)$ is required in the construction of prefixSum and $O(1)$ time required to answer each query.

Space Complexity – Since, we require an array of size $n$ to store the prefixSum the space complexity of the solution is $O(n)$.

Use Cases and Application of Prefix Sum

• Equilibrium index of an array – The equilibrium index can be defined as the index in the array such that the sum of elements of lower indices is equal to the sum of elements of higher indices.
  This can easily be found by traversing the prefixSum array once and for each index i checking if the sum of range [0, i] is equal to the sum of range [i+1, n - 1].
• Find if there exists a subarray with sum 0 – Given an array consisting of integers (possibly negative integers). Check if there exists a non-empty subarray such that the sum of elements in it is 0.
  This can be checked using the prefixSum and some simple hashing concepts.
• Find the minimum farthest checkpoint reachable – Given a card with a certain amount of fuel, find the farthest reachable approach if it costs 1 unit of fuel in covering 1 unit of distance.
  The brute force apporach requires $O(n)$ time, while if we use the concept of prefixSum and binary search it can be optimized to $O(\log{n})$.

Conclusion

• Prefix sum is the array constructed based on the values of another array (provided as input).
• Each index of prefixSum array contains the sum of elements of the subarray that starts at the $0^{th}$ index and ends at $i^{th}$ index.
• The concept of prefix sum can be used in solving a variety of problems efficiently.

FAQs

Q. What Should be Done if we have Quite Large Values given in the Array?

A. In such cases, it is advisable to declare prefixSum array such that it can hold 64-bit integers. This is done so that values do not overflow.

Q. Is there any PrefixSum for a 2-D Array?

A. Yes, there exists prefixSum for 2-D arrays also. They are represented as 2-D array, where prefixSum[i][j] consists of sum of all elements a[x][y] such that 0 <= x <= i and 0 <= y <= j.