How to find prefix sum

#1

In “Sum of All Submatrix in a given matrix - Approach 2”
how do i find prefix sum…

#2

Yes @alok.maurya,

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];
}
}

It’s the same we have learned in case of subarray with maximum sum.
But, you have to consider the 2D matrix here

Basically,
prefix sum at index (i,j) is the sum of all the elements within the submatrix (0,0){top left index} to (i,j){bottom right index}.

1 Like