二维树状数组理解 单点修改,区间查询
一维树状数组相比普通数组,将部分元素替换成区间和,以实现log查询区间和和log修改能用于在线操作;普通数组只能O(n)查询区间和。
二维树状数组也是一样的,建立二维数组,将数组部分元素用区间和代替,实现log查询sum。
位置p对p+lowbit(p)…有贡献,所以每次添加把所有(x,y)对应的位置增加(对其都有贡献)。
eg:a数组内容全是1,其seg如下图。
区间修改,单点查询 https://loj.ac/p/134
维护差分数组即可
区间修改,区间查询 https://loj.ac/p/135
类比一维树状数组,差分数组b实现区间修改,区间查询转化求解
如下图每个位置被加了多少次
sum=$\sum$$\sum$a[i][j]=$\sum$$\sum$cnt(b[i][j])=$\sum$$\sum$(x+1-i)(y+1-j)b[i][j] (几何降维转化)
=$\sum$$\sum$(x+1)(y+1)b[i][j]+$\sum$$\sum$ijb[i][j]-$\sum$$\sum$(x+1)jb[i][j]-$\sum$$\sum$(y+1)ib[i][j]
=(x+1)(y+1)cnt(i,j)+cntij(i,j)-(x+1)cntj(i,j)-(y+1)cnti(i,j)
共需要维护b,ib,jb,ijb四个树状数组。
#include <iostream>
#include <algorithm>
typedef long long ll;
using namespace std;
const int N = 5000;
ll seg[N][N], n, m;
void add(int x, int y, ll k) {
for (int i = x; i <= n; i += i & -i) {
for (int j = y; j <= m; j += j & -j) {
seg[i][j] += k;
}
}
}
ll count(int x, int y) {
ll res = 0;
for (int i = x; i > 0; i -= i & -i) {
for (int j = y; j > 0; j -= j & -j) {
res += seg[i][j];
}
}
return res;
}
int main() {
cin >> n >> m;
int a, b, c, d;
ll k;
while (cin >> c) {
if (c == 1) {
cin >> a >> b >> k;
add(a, b, k);
} else {
cin >> a >> b >> c >> d;
cout << count(c, d) - count(a - 1, d) - count(c, b - 1) + count(a - 1, b - 1) << endl;
}
}
}