前置知识：树状数组学习

二维树状数组简介

二维树状数组用于处理二维数组中的查询和修改。和一维树状数组一样，二维树状数组代码短，常数和空间小，时间复杂度小，十分方便好用。

设原数组上的点为a[i][j]a[i][j]a[i][j]，二维树状数组上的点为s[i][j]s[i][j]s[i][j]，则

s[x][y]=∑i=txx∑j=tyya[i][j]s[x][y]=\sum\limits_{i=tx}^x\sum\limits_{j=ty}^y a[i][j]s[x][y]=i=tx∑x​j=ty∑y​a[i][j]

其中tx=x−2m+1tx=x-2^m+1tx=x−2m+1，ty=y−2n+1ty=y-2^n+1ty=y−2n+1
mmm表示xxx的二进制中末尾连续的0的个数，nnn表示yyy的二进制中末尾连续的0的个数。

二维树状数组的操作

单点修改

和一维树状数组类似，修改a[i][j]a[i][j]a[i][j]，要将所有含有a[i][j]a[i][j]a[i][j]的s[i][j]s[i][j]s[i][j]都修改。

code

void add(int x,int y,long long v){for(int i=x;i<=n;i+=lb(i)){for(int j=y;j<=m;j+=lb(j)){tr[i][j]+=v;}}
}

时间复杂度为O(log⁡2n)O(\log^2 n)O(log2n)

区间查询

求aaa数组的二维前缀和，和一维树状数组的求法类似。

code

long long find(int x,int y){long long re=0;for(int i=x;i;i-=lb(i)){for(int j=y;j;j-=lb(j)){re+=tr[i][j];}}return re;
}

若要求∑i=ac∑j=bda[i][j]\sum\limits_{i=a}^c\sum\limits_{j=b}^d a[i][j]i=a∑c​j=b∑d​a[i][j]，则答案为find(c,d)−find(c−1,b)−find(a−1,d)+find(a−1,b−1)find(c,d)-find(c-1,b)-find(a-1,d)+find(a-1,b-1)find(c,d)−find(c−1,b)−find(a−1,d)+find(a−1,b−1)。可以画图理解。

时间复杂度为O(log⁡2n)O(\log^2 n)O(log2n)

例题

单点修改+区间查询模板的代码就是上面两个代码拼接起来，这里不再赘述。下面给一道有难度的题。

洛谷 P4514 上帝造题的七分钟

这道题涉及到区间查询和区间修改。

和一维树状数组一样，设ddd数组为aaa数组的差分，即d[i][j]=a[i][j]−a[i−1][j]−a[i][j−1]+a[i−1][j−1]d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]d[i][j]=a[i][j]−a[i−1][j]−a[i][j−1]+a[i−1][j−1]

则a[x][y]=∑i=1x∑j=1yd[i][j]a[x][y]=\sum\limits_{i=1}^x\sum\limits_{j=1}^y d[i][j]a[x][y]=i=1∑x​j=1∑y​d[i][j]

对于区间修改，设将(a,b)(a,b)(a,b)和(c,d)(c,d)(c,d)为顶点的矩形内每个数都增加vvv，则d[c][d]+=v,d[c][b−1]−=v,d[a−1][d]−=v,d[a−1][b−1]+=vd[c][d]+=v,d[c][b-1]-=v,d[a-1][d]-=v,d[a-1][b-1]+=vd[c][d]+=v,d[c][b−1]−=v,d[a−1][d]−=v,d[a−1][b−1]+=v即可，这样就变成了单点修改。

对于区间查询：
sum[x][y]=∑i=1x∑j=1ya[i][j]sum[x][y]=\sum\limits_{i=1}^x\sum\limits_{j=1}^y a[i][j]sum[x][y]=i=1∑x​j=1∑y​a[i][j]
=∑i=1x∑j=1y∑i′=1i∑j′=1jd[i′][j′]\qquad \qquad \ \ =\sum\limits_{i=1}^x\sum\limits_{j=1}^y\sum\limits_{i'=1}^i\sum\limits_{j'=1}^j d[i'][j']  =i=1∑x​j=1∑y​i′=1∑i​j′=1∑j​d[i′][j′]
=∑i=1x∑j=1yd[i][j]∗(x−i+1)∗(y−j+1)\qquad \qquad \ \ =\sum\limits_{i=1}^x\sum\limits_{j=1}^yd[i][j]*(x-i+1)*(y-j+1)  =i=1∑x​j=1∑y​d[i][j]∗(x−i+1)∗(y−j+1)
=(x+1)(y+1)∑i=1x∑j=1yd[i][j]−(y+1)∑i=1x∑j=1yd[i][j]∗i−(x+1)∑i=1x∑j=1yd[i][j]∗j+∑i=1x∑j=1yd[i][j]∗i∗j\qquad \qquad \ \ =(x+1)(y+1)\sum\limits_{i=1}^x\sum\limits_{j=1}^yd[i][j]-(y+1)\sum\limits_{i=1}^x\sum\limits_{j=1}^yd[i][j]*i-(x+1)\sum\limits_{i=1}^x\sum\limits_{j=1}^yd[i][j]*j+\sum\limits_{i=1}^x\sum\limits_{j=1}^yd[i][j]*i*j  =(x+1)(y+1)i=1∑x​j=1∑y​d[i][j]−(y+1)i=1∑x​j=1∑y​d[i][j]∗i−(x+1)i=1∑x​j=1∑y​d[i][j]∗j+i=1∑x​j=1∑y​d[i][j]∗i∗j

所以，我们需要维护d[i][j],d[i][j]∗i,d[i][j]∗j,d[i][j]∗i∗jd[i][j],d[i][j]*i,d[i][j]*j,d[i][j]*i*jd[i][j],d[i][j]∗i,d[i][j]∗j,d[i][j]∗i∗j的前缀和，即可求出a[i][j]a[i][j]a[i][j]的和。

code

#include
using namespace std;
int n,m,tr[2505][2505][4];
char ch;
int lb(int i){return i&(-i);
}
void add(int x,int y,long long v){for(int i=x;i<=n;i+=lb(i)){for(int j=y;j<=m;j+=lb(j)){tr[i][j][0]+=v;tr[i][j][1]+=v*x;tr[i][j][2]+=v*y;tr[i][j][3]+=v*x*y;}}
}
long long find(int x,int y,int z){long long re=0;for(int i=x;i;i-=lb(i)){for(int j=y;j;j-=lb(j)){re+=tr[i][j][z];}}return re;
}
long long sum(int x,int y){return (x+1)*(y+1)*find(x,y,0)-(y+1)*find(x,y,1)-(x+1)*find(x,y,2)+find(x,y,3);
}
int main()
{int a,b,c,d;long long v;scanf("%c%d%d",&ch,&n,&m);while(scanf("%c",&ch)!=EOF){if(ch!='L'&&ch!='k') continue;if(ch=='L'){scanf("%d%d%d%d%d",&a,&b,&c,&d,&v);add(a,b,v);add(c+1,b,-v);add(a,d+1,-v);add(c+1,d+1,v);}else{scanf("%d%d%d%d",&a,&b,&c,&d);printf("%d\n",sum(c,d)-sum(c,b-1)-sum(a-1,d)+sum(a-1,b-1));}}return 0;
}