Editorial

Let $a$ be the input array, $s$ be the array of partial sums. We shall fill the array $s$ 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 $s$ are already computed up to $s_{i,j}$.

Then

Example

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

Exercise

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

Algorithm realization

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");
}