If you are given an array A with elements [-2,6,4,1,8] and you need to find the sum of subarray. How will you find?

Let's say you need to find the sum from index i to index j. You can find by iterating from index i to index j and adding all the elements. And time complexity will be O(N).

sum=0;
for(int m=i; m<=j;m++){
   sum=sum+A[m];
}

Let's assume we have total q queries, How we will find the sum for each and every query?

We have to write one for loop for iterating upto q no. of queries and inside that for loop we have to find the sum of the range[i,j] of elements in the given query.

for(int c=0;c<q;c++){
   sum=0;
   for(int m=i; m<=j;m++){
       sum=sum+A[m];
   } 
}

Here the time complexity will be O(Q.N).

Now the queries any user can give could be infinite. So this would become worse time complexity. In order to tackle this problem, we could use Prefix sum.

Let's take another example, you are watching the game of cricket and at every over, you're noting 📝 down total runs scored by the team. Let's say this is the score you have noted [6,8,20,24,34,44,56,72,82,100]. Now if I ask you what is score that team scored between over 2 to 5. How will you calculate? You will subtract total score of team after completion of 5th over with total score of team at 1st over. You'll give answer 34-6 = 28.

How will you calculate score after over 10 completion? It will last element that is 100.

How will you calculate score from 4 to 7th over? {Score after 7th over - score at 3rd over}

Similarly, If we need to calculate score from over i to over J. We could calculate this in O(1) by just subtracting element at j with element at (i-1).

Now, Let's consider our 1st example.

If you are given an array A with elements [-2,6,4,1,8] and you need to find the sum of subarray. How will you find?

=> We can now come with a approach where we can create another array with the sum of element till ith position. Now, We will come up with this array:

A' = [-2, 4, 8, 9, 17]

This is called prefix sum.

Now, if we need to find the sum of elements from ith position to jth position, we could just subtract element at jth position in new array A' with element at (i-1)th position in A'.

Now if we have hundred queries then we could get the answer in O(1) time complexity.

The time complexity of whole algorithm is reduced to O(q + N).

Whenever, we are given sum in the range, the first thing that should strike in our mind is prefix sum, as it could help us in solving the problem in much easier way.

------‐-------------------------