（二维树状数组）POJ

原题链接：http://poj.org/problem?id=2155

题意：一个n*n的矩阵，有q次询问两种操作，一种是选定一个子矩阵，0变1,1变0，还有一种是查询某个位置的值，初始为全0

分析：01互换很容易想到异或，及需要将树状数组的模板略作修改，如下：

 1 int sum(int x, int y) {
 2     int ret = 0;
 3     for (int i = x; i > 0; i -= lowbit(i)) {
 4         for (int j = y; j > 0; j -= lowbit(j)) {
 5             ret ^= bit[i][j];
 6         }
 7     }
 8     return ret;
 9 }
10 
11 void change(int x, int y, int d) {
12     for (int i = x; i <= n; i += lowbit(i)) {
13         for (int j = y; j <= n; j += lowbit(j)) {
14             bit[i][j] ^= d;
15         }
16     }
17 }

由于第一次写二维的树状数组，二维的循环写错了，一直无法过样例。无奈看了题解。

对题解中计数的方法也是格外佩服。

这才是能用未知的题目转化为已学的知识，这才是大牛，分分钟举一反三，而不不形成思维定势。

代码：

 1 const int maxn = 1001;
 2 int bit[maxn][maxn];
 3 int n;
 4 
 5 int lowbit(int x) {
 6     return x&-x;
 7 }
 8 
 9 //此处省略部分函数
10 
11 void solve() {
12     int t;
13     cin >> t;
14     while (t--) {
15         memset(bit, 0, sizeof(bit));
16         int  q;
17         cin >> n >> q;
18         string op;
19         int x1, y1, x2, y2;
20         for (int i = 0; i < q; i++) {
21             cin >> op;
22             if (op == "C") {
23                 cin >> x1 >> y1 >> x2 >> y2;
24                 change(x1, y1, 1);
25                 change(x2 + 1, y1, 1);
26                 change(x1, y2 + 1, 1);
27                 change(x2 + 1, y2 + 1, 1);
28             }
29             else {
30                 cin >> x1 >> y1;
31                 cout << sum(x1, y1)  << endl;
32             }
33         }
34         if (t != 0)cout << endl;
35     }
36 }

大牛的计数方法，虽然很简单，但是对以后的发散性思维的养成也很有帮助。

 1 const int maxn = 1001;
 2 int bit[maxn][maxn];
 3 int n;
 4 
 5 int lowbit(int x) {
 6     return x&-x;
 7 }
 8 
 9 int sum(int x, int y) {
10     int ret = 0;
11     for (int i = x; i > 0; i -= lowbit(i)) {
12         for (int j = y; j > 0; j -= lowbit(j)) {
13             ret += bit[i][j];
14         }
15     }
16     return ret;
17 }
18 
19 void change(int x, int y, int d) {
20     for (int i = x; i <= n; i += lowbit(i) ){
21         for (int j = y; j <= n; j += lowbit(j)) {
22             bit[i][j] +=d;
23         }
24     }
25 }
26 
27 void solve() {
28     int t;
29     cin >> t;
30     while (t--) {
31         memset(bit, 0, sizeof(bit));
32         int  q;
33         cin >> n >> q;
34         string op;
35         int x1, y1, x2, y2;
36         for (int i = 0; i < q; i++) {
37             cin >> op;
38             if (op == "C") {
39                 cin >> x1 >> y1 >> x2 >> y2;
40                 change(x1, y1, 1);
41                 change(x2 + 1, y1, 1);
42                 change(x1, y2 + 1, 1);
43                 change(x2 + 1, y2 + 1, 1);
44             }
45             else {
46                 cin >> x1 >> y1;
47                 cout << sum(x1, y1) % 2 << endl;
48             }
49         }
50         if (t != 0)cout << endl;
51     }
52 }