AcWing 1269. 二维树状数组 实现 单点修改 与 区间查询
原题链接
中等
作者:
Snrise
,
2024-04-01 21:30:14
,
所有人可见
,
阅读 3
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1050;
int tr[N][N];
int n, m;
int lowbit(int x)
{
return x & -x;
}
void add(int x, int y, int a)
{
for (int i = x; i <= n; i += lowbit(i))
{
for (int j = y; j <= n; j += lowbit(j))
{
tr[i][j] += a;
}
}
}
int sum(int x, int y)
{
int ans = 0;
for (int i = x; i >= 1; i -= lowbit(i))
{
for (int j = y; j >= 1; j -= lowbit(j))
{
ans += tr[i][j];
}
}
return ans;
}
signed main(void)
{
std::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++;
add(x, y, k);
}
else
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
x1++, y1++, x2++, y2++;
cout << sum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) + sum(x1 - 1, y1 - 1) << endl;
}
}
return 0;
}