Prefix Sum
Overview
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].
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 index of this newly formed array denotes the sum of the subarray of arr that starts from the index and ends at the 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.
i | Calculation | prefixSum[i] |
---|---|---|
0 | 3 | 3 |
1 | 3 + 2 | 5 |
2 | 3 + 2 + 1 | 6 |
3 | 3 + 2 + 1 + 5 | 11 |
4 | 3 + 2 + 1 + 5 + 4 | 15 |
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 -
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 , which can be easily optimized to 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 and due to some reason we already calculated the sum of in the past. Now we have two options -
- Calculate the sum of all elements again.
- Or use the associative property of addition
Obviously the latter requires much fewer calculations as we already have the value and we just need to add 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, in all cases because it is the first element. And, for all other indices i the prefix sum can be calculated using the formula because while calculating the we already had calculated . Therefore, to calculate the prefixSum[i] i.e. we just need to add a[i] in .
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
Output -
C++ Implementation
Output -
Python Implementation
Output -
Complexity Analysis
Time Complexity - Since, we are traversing the array only once, which requires steps. Therefore, the time complexity is .
Space Complexity - An array of size is required to store the answer. Therefore the space complexity is .
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 . Where means sum array elements whose indices are in range a[l] + a[l+1] + ... + a[r]. The brute force method is to find the sum using the for loop, which costs 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 , now we know that
and
Now, if we calculate
i.e. , we obtain the required answer i.e.
The steps required to find are -
- Let's say we have constructed the prefixSum array.
- For each query range sum query do the following -
- If l = 0, simply return prefixSum[r].
- Otherwise return prefixSum[r] - prefixSum[l - 1].
Java Implementation
Output -
C++ Implementation
Output -
Python Implementation
Output -
Complexity Analysis
Time Complexity - If the size of the array is and we need to answer queries, the time complexity is . Where is required in the construction of prefixSum and time required to answer each query.
Space Complexity - Since, we require an array of size to store the prefixSum the space complexity of the solution is .
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 time, while if we use the concept of prefixSum and binary search it can be optimized to .
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 index and ends at 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.