prefix sum

Prefix Sum in Array

In Previous post we already discuss about sliding window technique and problem, in this post we are going to know about prefix sum technique in array

Let us Consider an example, we are given an array of integers and we have to find the range query sum of it, which means we are given some k number of Queries which takes two values l and r and we have to find the sum of elements present in this range (both inclusive). 

Let’s illustrate the problem statement more clearly, 

Let the array be, arr[5] = {4, 7, 2, 9, 5} and k = 3 is given, 

{2, 4}, { 3, 3},{  1, 5}

These are the range Queries and we have to find the sum of all the range queries

Output : 18 2 27  

Naive Method

The Naive method to solve this problem is to run two loops, first for iterating k   number of queries and second to find the actual sum between the range of the query. 

Code

void Sum (int *arr, int k)
{
	int l, r;
	for(int i = 1; i <= k; i++){
		cin >> l >> r;
		int sum = 0;
		for(int j = l; j <= r; j++){
			sum = sum + arr[j];
		}
		cout<<sum<<” “;
	}
}

Analysis of Complexity of the Naive Solution

Calculation of sum between range takes O(n) time complexity in worst case.

  To perform k number of Queries on n size Array,  Time Complexity :

O(k*n) 

But Prefix Sum Algorithm does the same task,  Time Complexity : O(n) 

Algorithm of Prefix Sum

The idea of the Prefix Sum Algorithm is to transform an array in O(n) time complexity such that the difference of (arr[l]-arr[r]) gives us the desired result.   

Since Subtraction operation takes O(1) time, so overall time complexity would be  O(n*1). 

Now the question arises, how do we transform the array to perform this task? 

Sadly, there is no magic that will transform the array for us to perform this task.  We only have to think of some calculations which will transform it. 

Don’t worry we will discuss the logic here but it is highly recommended to first think it yourself. If you found any algorithm, congrats.

But if not don’t worry, we will discuss it. 

4 7 2 9 5

This was the array we had previously,

We will create a prefix sum array where we will store the prefix sum values. Prefix sum is the sum of the array values till that point. For ex :- arr[2] = 11 ( 4 + 7).

4 11 13 22 27

This is the prefixSum[ ] array where we store prefix sum values at every index.

This prefixSum array will help us to solve the Range Sum query problem.

Let us take a query where l = 2 and r = 5.

Step 1 : We know that prefixSum[2] = 11 and prefixSum[5] = 27.

Step 2 : Calculate prefixSum[5] – prefixSum[2-1].

Finally : We got the desired result of this Query.

This looks quite simple and believes it, this Algorithm follows these steps only.

Code for prefix sum

void Sum (int *arr, int k, int n)
{
	int prefixSum[n+1];			
	int sum = 0, result;
	for(int i = 1; i <= n; i++){
		sum += arr[i];
		prefixSum[i] = sum;
	}
	for(int i = 1; i <= k; i++){
		cin >> l >> r;
		if ( l == 0) result = prefixSum[r];
		else result = prefixSum[r] - prefixSum[l-1];
		cout<<result<<” “;
	}
}

Analysis of Prefix Sum Algorithm

This is a two step Algorithm, first we create prefixSum[ ] array,

Time Complexity : O(n)

Secondly we just find the result for each Query,

Time Complexity : O(k)

Overall Time Complexity : O(n+k)

We observed that we solved the Range Query Problem in just Linear time complexity which is quite better than Quadratic Time Complexity. 

Logic Behind Prefix Sum Algorithm (MasterStroke)

We have observed that we are getting the desired result of Range Sum Query in Linear time after solving it through the prefix Sum Algorithm but why are we getting the result, what is the logic behind it?

Let us consider the example again,

4 7 2 9 5

Let us also take a query l = 3 and r = 5.

We need to find the sum of this query, which would be 2+9+5 = 16 and we can find it by simply running a loop from arr[l] to arr[r] and find its sum.

But if we observe carefully, we can also get the desired result by subtracting the total sum with the sum of the range which is not included in (l, r).

Total sum : 4 + 7 + 2 + 9 + 5 = 27

Sum of range which is not included in (l, r) : 4 + 7 = 11

Result : 27 – 11 = 16

This is the main logic of Prefix Sum Algorithm, we first pre-calculate the prefixSum and store it in array prefixSum[ ].

Now since we know the range (l, r) and also we know the total sum of the array element up to r ( prefixSum[r]), we simply need to subtract it with the sum of the elements which are not included in the range, which means prefixSum[l-1].

prefixSum[l-1] stores the sum of elements included in the range (1, l-1).

Hope you all understand the logic behind the Prefix Sum Algorithm. Prefix Sum Algorithm is quite a useful Algorithm to solve Range Query Problems and many other interview problems.

Sudhanshu is Technology geek and also a pro pubg player. I like to create content in my free time that helps others. Currently pursuing BCA from Noida and operating Geekstocode

Leave a Comment

Your email address will not be published. Required fields are marked *