Prefix Sum : Query Time O(1) : Pre-processing Time O(n)

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).