题目大意
快速求二维前缀和,快速修改矩阵中某个元素
解题思路
二维树状数组模板
具体代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1050;
int n, m;
LL c[N][N];
void add(int x, int y, int t)
{
for (int i = x; i <= n; i += i & -i)
for (int j = y; j <= n; j += j & -j)
c[i][j] += t;
}
LL query(int x, int y)
{
LL res = 0;
for (int i = x; i; i -= i & -i)
for (int j = y; j; j -= j & -j)
res += c[i][j];
return res;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
while (cin >> m, m != 3)
{
if (m == 1)
{
int x, y, k;
cin >> x >> y >> k;
x++, y++; //树状数组碰到0是会死循环的,因为0的lowbit还是0
add(x, y, k);
}
else
{
int x1, x2, y1, y2;
cin >> x1 >> y1 >> x2 >> y2;
x1++, y1++, x2++, y2++;
cout << query(x2, y2) - query(x2, y1 - 1) - query(x1 - 1, y2) + query(x1 - 1, y1 - 1) << '\n';
//和普通的二维前缀和求法是一样的
}
}
return 0;
}