二维树状数组的维护
【例题】
【题解】很明显对于50个物品分奇偶性状压即可,然后用异或维护。剩下的就是二维维护问题了。
简单的二维树状数组,能维护单点的修改和区间的求和。
比如如下代码
struct BIT_2D { ll c[M][M]; inline void init() { memset(c, 0, sizeof(c)); } inline void change(int x, int y, ll del) { for (int i=x; i<=n; i+=lowbit(i)) for (int j=y; j<=n; j+=lowbit(j)) c[i][j] ^= del; } inline ll sum(int x, int y) { ll ret=0; for (int i=x; i>0; i-=lowbit(i)) for (int j=y; j>0; j-=lowbit(j)) ret ^= c[i][j]; return ret; } };
相信大家如果学过一维树状数组的都能理解。
然后考虑如何拓展成二维情况。
我们先回顾下一维的时候是怎么做的:$b_i$表示$[i,n]$整体加了多少,然后通过维护$b_i$和b_i\times i$来维护区间修改与求和。
那么二维呢?一样的!
设$b_{i,j}$表示$(i,j)-(n,n)$这块矩形区域整体加了多少,那么设面积前缀和为$S'(x,y)$,则
$S'(x,y)=\sum_{i\leq x~and~j \leq y} a_{i,j} + \sum_{i\leq x~and~j\leq y}(b_{i,j} \times (x-i+1) \times(y-j+1))$。
展开可得
$S'(x,y)=\sum_{i\leq x~and~j \leq y} a_{i,j} + \sum_{i\leq x~and~j\leq y} b_{i,j} \times (x-i+1) \times(y-j+1) $
$~~~~~~~~~~~~~~~~- \sum_{i\leq x~and~j\leq y}(b_{i,j} \times i)\times (y+1)- \sum_{i\leq x~and~j\leq y}(b_{i,j} \times j) \times (x+1) $
我们发现,可以类似于一维树状数组维护四个值即可:$b_{i,j}$,$b_{i,j} \times j$,$b_{i,j} \times i$,$b_{i,j}\times i\times j$。
那么考虑对于区间$(x_1, y_1)$到$(x_2,y_2)$的查询,就可以写出如下式子:
$S = S'(x_2, y_2) - S'(x_2, y_1-1) - S'(x_1-1, y_2) + S'(x_1-1, y_1-1)$。
所以我们会写查询辣!
然后发现区间修改不会???
听说你不会???
再次考虑$b_{i,j}$的含义:表示$(i,j)-(n,n)$这块矩形区域整体加了多少。
那么对于区间$(x_1, y_1)$到$(x_2,y_2)$的增加,就可以转化成四个$b_{i,j}$的分别变化啦
啥?你问我哪四个?$b_{x2+1, y2+1}$,$b_{x1, y2+1}$,$b_{x2+1,y1}$,$b_{x1,y1}$。
啥?你问我怎么变化?四个树状数组相应变化,所以一共要改16次,查询也一样。
啥?你问我这题怎么做?加和减全替换成异或就行了!
贴代码
# include <stdio.h> # include <algorithm> # include <string.h> # define lowbit(x) ((x)&(-x)) using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 3010; char opt[10]; int n, m; struct BIT_2D { ll c[M][M]; inline void init() { memset(c, 0, sizeof(c)); } inline void change(int x, int y, ll del) { for (int i=x; i<=n; i+=lowbit(i)) for (int j=y; j<=n; j+=lowbit(j)) c[i][j] ^= del; } inline ll sum(int x, int y) { ll ret=0; for (int i=x; i>0; i-=lowbit(i)) for (int j=y; j>0; j-=lowbit(j)) ret ^= c[i][j]; return ret; } }; struct BIT2D { BIT_2D b, bi, bj, bij; void init() { b.init(); bij.init(); bi.init(); bj.init(); } inline void change(int posx, int posy, ll del) { b.change(posx, posy, del); if(posx&1) bi.change(posx, posy, del); if(posy&1) bj.change(posx, posy, del); if((posx*posy) & 1) bij.change(posx, posy, del); } inline void Change(int x1, int y1, int x2, int y2, ll del) { change(x2+1, y2+1, del); change(x2+1, y1, del); change(x1, y2+1, del); change(x1, y1, del); } inline ll sum(int posx, int posy) { ll ret = 0; if(((posx+1)*(posy+1))&1) ret ^= b.sum(posx, posy); if((posy+1)&1) ret ^= bi.sum(posx, posy); if((posx+1)&1) ret ^= bj.sum(posx, posy); ret ^= bij.sum(posx, posy); return ret; } inline ll Sum(int x1, int y1, int x2, int y2) { ll ret = 0; ret ^= sum(x2, y2); ret ^= sum(x1-1, y2); ret ^= sum(x2, y1-1); ret ^= sum(x1-1, y1-1); return ret; } }T; int main() { freopen("treasure.in", "r", stdin); freopen("treasure.out", "w", stdout); scanf("%d%d", &n, &m); T.init(); while(m--) { scanf("%s", opt); if(opt[0] == 'P') { int X1, X2, Y1, Y2, k; ll res = 0; scanf("%d%d%d%d", &X1, &Y1, &X2, &Y2); scanf("%d", &k); while(k--) { int a, b; scanf("%d%d", &a, &b); if(b&1) res ^= 1ll<<(a-1); } T.Change(X1, Y1, X2, Y2, res); } else { int X1, X2, Y1, Y2, op[50]; scanf("%d%d%d%d", &X1, &Y1, &X2, &Y2); ll res = T.Sum(X1, Y1, X2, Y2); for (int i=0; i<50; ++i) op[i] = (res&(1ll<<i)) ? 2 : 1; printf("%d", op[0]); for (int i=1; i<50; ++i) printf(" %d", op[i]); puts(""); } } return 0; }