1029. Matrix Summation

A n × n matrix is filled with numbers. BuggyD is analyzing the matrix, and he wants the sum of certain submatrices every now and then, so he wants a system where he can get his results from a query. Also, the matrix is dynamic, and the value of any cell can be changed with a command in such a system.

Assume that initially, all the cells of the matrix are filled with 0. Design such a system for BuggyD. Read the input format for further details.

Input. The first line of the input contains an integer t, the number of test cases. t test cases follow.

The first line of each test case contains a single integer n (1 ≤ n ≤ 1024), denoting the size of the matrix.

A list of commands follows, which will be in one of the following three formats (quotes are for clarity):

· "SET x y num" - Set the value at cell (x, y) to num (0 ≤ x, y < n).

· "SUM x₁ y₁ x₂ y₂" - Find and print the sum of the values in the rectangle from (x₁, y₁) to (x₂, y₂), inclusive. You may assume that x₁ ≤ x₂ and y₁ ≤ y₂, and that the result will fit in a signed 32-bit integer.

· "END" - Indicates the end of the test case.

Output. For each test case, output one line for the answer to each "SUM" command. Print a blank line after each test case.

Sample Input

1

4

SET 0 0 1

SUM 0 0 3 3

SET 2 2 12

SUM 2 2 2 2

SUM 2 2 3 3

SUM 0 0 2 2

END

Sample Output

1

12

12

13

РЕШЕНИЕ

структуры данных – дерево Фенвика двумерное

Анализ алгоритма

Пусть mat – текущая матрица. Построим для нее двумерное дерево Фенвика t. Пусть sum(x, y) – это функция, которая находит сумму чисел на прямоугольнике (0, 0) – (x, y) при помощи дерева Фенвика за время O(). Тогда сумма чисел на прямоугольнике (x₁, y₁) – (x₂, y₂) равна

sum(x₂, y₂) – sum(x₁ – 1, y₂) – sum(x₂, y₁ – 1) + sum(x₁ – 1, y₁ – 1)

Присвоение mat[x][y] = num эквивалентно прибавлению к mat[x][y] значения num – mat[x][y] (дерево Фенвика реализует только операцию прибавления на отрезке, а не присваивание).

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

#include <cstdio>

#include <vector>

#include <cstring>

using namespace std;

vector<vector<int> > t, mat;

int n, tests;

// sum of rectangle a[0, 0] - a[x, y]

int sum(int x, int y)

{

int result = 0;

for (int i = x; i >= 0; i = (i & (i + 1)) - 1)

for (int j = y; j >= 0; j = (j & (j + 1)) - 1)

result += t[i][j];

return result;

}

// a[x][y] += delta

void add(int x, int y, int delta)

{

for (int i = x; i < n; i = (i | (i+1)))

for (int j = y; j < n; j = (j | (j+1)))

t[i][j] += delta;

}

char s[10];

int x, y, x1, y1, x2, y2, num, res;

int main (void)

{

scanf("%d",&tests);

while(tests--)

{

scanf("%d",&n);

t.assign(n+1,vector<int>(n+1,0));

mat.assign(n+1,vector<int>(n+1,0));

while(scanf("%s ",s),strcmp(s,"END"))

{

if (s[1] == 'E') // set

{

scanf("%d %d %d",&x,&y,&num);

if (mat[x][y] != num)

{

add(x,y,num - mat[x][y]);

mat[x][y] = num;

}

} else // sum

{

scanf("%d %d %d %d",&x1,&y1,&x2,&y2);

res = sum(x2,y2) - sum(x1-1,y2) - sum(x2,y1-1) + sum(x1-1,y1-1);

printf("%d\n",res);

}

}

}

return 0;

}