Sum of all submatrix from a given matrix - approach 2

#1

how to convert matrix to prefix matrix

#2

hello @mohitsharmakosi2001

For prefix sum of 1D 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

Now 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]

See the following code segment to understand it:

//First add the values along column
for(int i=0;i<r;i++){
for(int j=1;j<c;j++){
a[i][j]+=a[i][j-1];
}
}
//Then add the values along rows.
for(int j=0;j<c;j++){
for(int i=1;i<r;i++){
a[i][j]+=a[i-1][j];
}
}
#3

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.