二维树状数组的维护

tonyfang posted @ 2016年11月07日 22:50 in 随笔 with tags c++ OI , 2203 阅读

【例题】

    继被阿里巴巴用奇怪的方法得到了宝藏以后,四十大盗的继承人有了更加绝妙的宝藏储存方式——他们把宝藏埋在了一块可分成 $n \times n$ 网格的空地下,网格按$(1, 1), (1, 2) … (1, n), (2, 1) … (2, n) … (n, n)$的方式编号。宝藏物品总共有 50 种。大盗们特地开发了一套程序来管理这些宝藏。初始时地里没有物品,他们总共会操作 M 次,每一次都会选择这个大网格图的一个子矩形,操作分两种:
对于埋物品操作,会给出一个物品序列,如“5 件 A、7 件 C” ,程序将会自动在这个子矩形的每一个方格内新添上述物品序列给出的物品(比如在(2, 2)里放 5 个 A、7 个 C,再在(2, 3)里放 5 个 A、7 个 C……) ;对于每个查询操作,需要打印一行 50 个整数,依次分别表示给定子矩形内每种物品数量的奇偶性。
现在,阿里巴巴的传人想要破解这套系统,首先就需要模拟以上程序的执行,你能帮助他吗?

【题解】很明显对于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) $

$~~~~~~~~~~~~~~~~- \sum_{i\leq x~and~j\leq y}(b_{i,j} \times i \times j)$

我们发现,可以类似于一维树状数组维护四个值即可:$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;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter