Partial matrix sum#683
Sign in

Partial matrix sum (Editorial)

Let be the input array, be the array of partial sums. We shall fill the array row by row in increasing order, and within each row, we shall process the cells in increasing order of columns. Assume that at this point, all values of the array are already computed up to s_{i,j}.

Then

s_{i,j} = s_{i - 1,j} + s_{i,j - 1} - s_{i - 1,j - 1} + a_{ij}

Example

Consider for the given example how to compute the value of s_{3,5}.

s_{3,5} = s_{2,5} + s_{3,4} – s_{2,4} + a_{3,5} = 30 + 35 – 24 + 4 = 45

Exercise

For the given array a_{ij} compute the values of the elements in the array s_{ij}.

Algorithm implementation

Declare two two-dimensional arrays.

#define MAX 1001
int a[MAX][MAX], s[MAX][MAX];

Read the input data.

scanf("%d %d",&n,&m);
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
  scanf("%d",&a[i][j]);

Compute the partial sums.

memset(s,0,sizeof(s));
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
  s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + a[i][j];

Print the resulting array of partial sums.

for(i = 1; i <= n; i++)
{
  for(j = 1; j <= m; j++)
    printf("%d ",s[i][j]);
  printf("\n");
}