Часткова сума матриці#683
Увійти

Часткова сума матриці (Розбір)

Нехай — вхідний масив, — масив часткових сум. Будемо заповнювати масив по рядках у порядку зростання, а комірки всередині кожного рядка — за зростанням стовпців. Припустимо, що на даний момент всі значення масиву вже обчислені аж до s_{i,j}.

Тоді

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

Приклад

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

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

Вправа

Для заданого масиву 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");
}