Разбор

Пусть $a$ — входной массив, $s$ — массив частичных сумм. Будем заполнять массив $s$ по строкам в порядке возрастания, а ячейки внутри каждой строки — по возрастанию столбцов. Предположим, что на данный момент все значения массива $s$ уже вычислены вплоть до $s_{i,j}$.

Тогда

Пример

Рассмотрим для заданного примера как вычислить значение $s_{3,5}$.

Упражнение

Для заданного массива $a_{ij}$ вычислите значения элементов массива $s_{ij}$.

Реализация алгоритма

Объявим два двумерных массива.

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

Читаем входные данные.

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

Вычисляем частичные суммы.

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

Выводим результирующий массив частичных сумм.

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