Problem in prefix array

#1

How will we find the prefix array?

#2

@akash_281, prefix sum of an array is the array where the ith element is the sum of prefix till ith index
eg :- arr[] ={1 2 3 4 5 6}
prefixSum[]={1 3 6 10 15 21}
prefixSum[0] = 1
prefixSum[1] = 1 + 2
prefixSum[2] = 1 + 2 + 3
prefixSum[3] = 1 + 2 + 3 + 4
prefixSum[4] = 1 + 2 + 3 + 4 + 5
prefixSum[5] = 1 + 2 + 3 + 4 + 5 +6

you can observe that
prefixSum[i] = prefixSum[i-1]+arr[i]
so using above formula you can calculate the prefix sum of an array in o(N)

In case of any doubt feel free to ask :slight_smile:
Mark your doubt as RESOLVED if you got the answer

#3

Hello sir,
This toh I understood but we are dealing with a 2d array now right? What you said was related to 1d array .

#4

okay , so you want to know about prefix sum matrix , in prefix sum matrix what we do is to make a matrix such that prefixSum[i][j] give us the sum of all the elements in the submatrix with top left index as (0,0) and bottom right index as (i,j) , we do this to find the sum of submatrix in o(1) when the topleft and bottom right indexes of the submatrix are known

Now to find prefix array you can simply use previously computed values to compute prefixSum[i][j]. Unlike 1D array prefix sum, this is tricky, here if we simply add prefixSum[i][j-1] and prefixSum[i-1][j], we get sum of elements from a[0][0] to a[i-1][j-1] twice, so we subtract prefixSum[i-1][j-1].

so , prefixSum[i][j]=prefixSum[i][j-1]+prefixSum[i-1][j]-prefixSum[i-1][j-1]

refer this code for better understanding :- https://ide.codingblocks.com/s/285374

1 Like