Written By : Shivani Tiwari
Range Sum is a popular problem in competitive programming and technical interviews. Range Sum problem asks sum of the elements in a range in a given array. Naïve approach requires O(N*Q) time which can be improved to be O(N+Q) using Prefix Sum approach. N is the size of the array and Q is the number of queries.
Prefix Sum technique is used to give range sum in an array in O(1) for each query with a one time pre-processing.
Let’s see an example for this with a basic statement.
Suppose you are given with an array of N integers (both negative and positive) and Q queries. Each query is of the form of two integers L and R where you have to find the sum of all the integers between L and R (inclusive).
Constraints : (N <= 10^5) , (1 <= L, R <= 10^5) and (Q <= 10^5)
Example : N=7, Q=3
Given Array : arr[]={4,5,-7,11,13,15,1}
arr–>
Sum of arr[0] to arr[4] is : 4+5+(-7)+11+13 = 26
Sum of arr[1] to arr[7] is : 5+(-7)+11= 9
Sum of arr[3] to arr[6] is : (-7)+11+13+15+1= 33
Naive Approach
For each query, let’s take a variable sum_range = 0 and run a loop from L to R index and store the sum in sum_range. We can do this for each query.
We will end up traversing the entire array length and there are Q such queries. So the time complexity would be O(N*Q). Therefore, this approach is inefficient.
Prefix Sum Approach
Pre-processing
Before answering any query, let’s calculate the cumulative sum of the array and store it in the array (let’s say prefix_array). The code for creating a prefix array would look like this :
prefix_array[1] = a[1]
{
for(i = 2; i <= n; ++i) {
prefix_array[i] = prefix_array[i-1] + a[i];
}
}
prefix_array–>
After creating this prefix array, each query of range (L, R) can be answered in O(1) by using
sum of arr[L] to arr[R] = prefix_array[R] – prefix_array[L-1]
Now the above queries can be answered in O(1) time as follows:
Sum of arr[1] to arr[5] = prefix_array[5] – prefix_array[0]
Sum of arr[2] to arr[4] = prefix_array[4] – prefix_array[1]
Sum of arr[3] to arr[7] = prefix_array[7] – prefix_array[2]
Key Idea : First take the cumulative sum from 0 to R and excluded the sum from 0 to L-1 from it, so the remaining sum is the sum from L to R.
Time complexity is O(N+Q).