Prefix sum method

#1

What is prefix sum technique…

#2

Hello @shamp@blocks,

Cumulative Sum(Prefix Sum):
A cumulative sum is a sequence of partial sums of a given sequence.
Example:
A[]={1,2,3,-1,5,6} //Original array
Cum_Sum[]={0,1,3,6,5,10,16} //Cumulative Sum
//An extra element 0 is added as first element because Cum_Sum of index i depends upon Cum_Sum of index i-1.

Cum_Sum[i]=Cum_Sum[i-1]+A[i-1]
//Here we are storing the Cum_Sum for index i=0 of array A[] at i=1 of Cum_Sum[]
//i.e. cumulative sum for index i of A[] at i+1 of Cum_Sum[]

Start i from 1 to 6(n):
Cum_Sum[0]=0
Cum_Sum[1]=Cum_Sum[0]+A[0]=0+1=1
Cum_Sum[2]=Cum_Sum[1]+A[1]=1+2=3
…
…So on

What is the significance of the Cumulative Sum:
We can find the sum of all elements of a subset of an array.
How?
Sum of elements of subset starting from the index i to j
Subset_Sum=Cum_Sum[j+1]-Cum_sum[i]=10-1=9
example:
Sum of elements of subset starting from the index i=1 to j=4
Subset_Sum=Cum_Sum[5]-Cum_sum[1]=10-1=9

You might find the formulas different from what they have taken in the video.
Don’t worry about that.
Just understand the concept that will help you to understand the difference.

Hope, this would help.
Give a like, if you are satisfied.

1 Like
#3

Thanks sir but i have a doubt Is it subset Or subarray in the example you mentioned…?

#4

Hello @shamp@blocks,

IT is a subarray.
In subarray, the elements are taken in continuous manner i.e. the order matters.
But in subsets, You can randomly have elements. They need not be consecutive in the original array.
Example:
{1,2,3}
Subarrays:
{1},{2}.{3}.{1,2},{2,3},{1,2,3}
Subsets:
{},{1},{2],{3},{1,2},{1,3},{2,3},{1,2,3}

Hope, this would help.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.