二维区间修改 + 区间修改
#include<bits/stdc++.h>
using namespace std;
const int N = 2050;
int t1[N][N],t2[N][N],t3[N][N],t4[N][N]; //4个二维树状数组
#define lowbit(x) ((x) & - (x))
int n,m;
void update(int x,int y,int d){
for(int i=x;i<=n;i+=lowbit(i)) //经典for嵌套
for(int j=y;j<=m;j+=lowbit(j)){
t1[i][j] += d; t2[i][j] += x*d; //修改二维树状数组的四个顶点
t3[i][j] += y*d; t4[i][j] += x*y*d; //更新4个二维树状数组
}
}
int sum(int x,int y){
int ans = 0;
for(int i=x;i>0;i-=lowbit(i))
for(int j=y;j>0;j-=lowbit(j))
ans += (x+1)*(y+1)*t1[i][j] - (y+1)*t2[i][j] - (x+1)*t3[i][j] + t4[i][j]; //10+11+18：D[i][j] = a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1]
return ans;
}
int main(){
char ch[2]; scanf("%s",ch);
scanf("%d%d",&n,&m); //设置矩阵大小
while(scanf("%s",ch)!=EOF){
int a,b,c,d,delta; scanf("%d%d%d%d",&a,&b,&c,&d);
if(ch[0]=='L'){
scanf("%d",&delta);
update(a, b, delta); update(c+1,d+1, delta); //差分数组方式修改树状数组区间
update(a, d+1,-delta); update(c+1,b, -delta);
}
else printf("%d\n",sum(c,d)+sum(a-1,b-1)-sum(a-1,d)-sum(c,b-1)); //
}
return 0;
}
笔记：二维区间修改用差分方式修改，树状数组储存，矩阵的区间和是：
$\sum_{i=a}^{c} \sum_{j=b}^{d}$a[i][j] = $\sum_{i=1}^{c} \sum_{j=1}^{d}$a[i][j] – $\sum_{i=1}^{c} \sum_{j=1}^{b-1}$a[i][j] – $\sum_{i=1}^{a-1} \sum_{j=1}^{d}$a[i][j] + $\sum_{i=1}^{a-1} \sum_{j=1}^{b-1}$a[i][j]
然后再拆，找到与差分数组的关系——
a[n][m] = $\sum_{i=1}^{n} \sum_{j=1}^{m}$a[i][j]
= $\sum_{i=1}^{n} \sum_{j=1}^{m}\sum_{k=1}^{i} \sum_{l=1}^{j}$d[k][l]
= $\sum_{i=1}^{n} \sum_{j=1}^{m}$d[i][j] × (n – i + 1) × (m – j + 1)
= (n +1)(m +1)$\sum_{i=1}^{n} \sum_{j=1}^{m}$d[i][j] – (m +1)$\sum_{i=1}^{n} \sum_{j=1}^{m}$d[i][j] × i – (n +1)$\sum_{i=1}^{n} \sum_{j=1}^{m}$d[i][j] × j + $\sum_{i=1}^{n} \sum_{j=1}^{m}$d[i][j] × i × j
以上是区间查询里四个二维树状数组的关系