Prefix Sum Array

prefix sum of an array we just need to take  the previous value of the prefix sum and add the current value of the traversed array. The idea behind is that in the previous position of the prefix array we will have the sum of the previous elements.  The prefix sum array of any array, arr[] is defined as an array of same size say, prefixSum[] such that the value at any index i in prefixSum[] is sum of all elements from indexes 0 to i in arr[].

That is,  

     

prefixSum[i] = arr[0] + arr[1] + arr[2] + . . . . + arr[i]

for all 0 <= i <= N.

Examples:

Input  : arr[] = {4,8,20,5,25}
Output : prefixSum[] = {4,12,32,37,62}

prefixSum[0]=arr[0]=>4

prefixSum[1]=arr[0]+arr[1]=>4+8=>12

prefixSum[2]=arr[0]+arr[1]+arr[2]=>12+20=>32

prefixSum[3]=arr[0]+arr[1]+arr[2]+arr[3]=>32+5=>37

prefixSum[4]=arr[0]+arr[1]+arr[2]+arr[3]+arr[4]=>37+25=>62

Below function generates a prefix sum array for a given array arr[] of size N:

void fillPrefixSum(int arr[], int N, int prefixSum[]) 
{ 
    prefixSum[0] = arr[0]; 
  
    // Adding present element  
    // with previous element 
    for (int i = 1; i < N; i++) 
        prefixSum[i] = prefixSum[i-1] + arr[i]; 
} 

This becomes really helpful because if you want to know what is the total sum up to certain point, you can just check for the value in the prefix sum array.

 We can easily calculate the sum with-in a range [i, j] in an array using the prefix sum array. 

Therefore, we can get the sum of elements in range [i,j] by:

prefixSum[j] - prefixSum[i-1]

The above formula will not work in the case when i = 0.

Therefore,

if i = 0
sumInRange = prefixSum[j]  

if (i != 0)
sumInRange = prefixSum[j] - prefixSum[i-1]