树状数组

什么是树状数组？
简单来说，就是暴力遍历数组来解决区间问题等，不过遍历的路径使用了位运算来进行压缩，复杂度是O(log2(n))这样就不会超时了（为所欲为？）。
lowbit()操作
其核心是神奇的lowbit操作，lowbit(x)=x&(-x)，它的功能是找到x的二进制数的最后一个1，原理是利用负数的补码表示，补码是原码取反加一。例如x=6=00000110(2)，-x=x补=11111010(2)，那么lowbit(x)=x&(-x)=10(2)=2。
从lowbit()引出数组a[]，a[x]的值是把ax(题目输入初始值)和他前面的m个数相加，如下表所示：

图形化：

那么通过数组a[]，就可以求sum,例如sum(8)=a[8]，sum(7)=a[7]+a[6]+a[4]，sum(6)=a[6]+a[4]，如此一来不就是我们要的路径压缩了吗？
同样地，更新ax时也要更新a[]，例如更新a3，那么首先更改a[3]；然后3+lowbit(3)=4,更改a[4]；接着4+lowbit(4)=8，更改a[8]。
二维树状数组
相应的，我们可以推导出二维树状数组，例如更新点求区间输入坐标(x,y),(u,v)求sum黄色区域，如下图所示：

由图易得所求区间黄色区域为sum(u,v)-sum(x-1,v)-sum(u,y-1)+sum(x-1,y-1)

例题

POJ-2155

Given an N*N matrix A, whose elements are either 0 or 1. A[i, j] means the number in the i-th row and j-th column. Initially we have A[i, j] = 0 (1 <= i, j <= N).
We can change the matrix in the following way. Given a rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2), we change all the elements in the rectangle by using “not” operation (if it is a ‘0’ then change it into ‘1’ otherwise change it into ‘0’). To maintain the information of the matrix, you are asked to write a program to receive and execute two kinds of instructions.
1 C x1 y1 x2 y2 (1 <= x1 <= x2 <= n, 1 <= y1 <= y2 <= n) changes the matrix by using the rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2).
2.Q x y (1 <= x, y <= n) querys A[x, y].

input:

The first line of the input is an integer X (X <= 10) representing the number of test cases. The following X blocks each represents a test case.

output:

For each querying output one line, which has an integer representing A[x, y].
There is a blank line between every two continuous test cases.

Sample Input:

Sample Output:

题意

在n*n矩阵中每次对一个子矩阵进行翻转（0变1,1变0），然后多次询问某个点是0还是1。

分析

更新区间求点，用二维树状数组解决，每次更新子矩阵+1，最后求点%2就得到结果。（其实就是二维数组模拟的思路，压缩路径罢了）。

代码

#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn = 1003;
char s[5];
int a[maxn][maxn], n;
int lowbit(int x) { 
    return (x & (-x));
}
void update(int x, int y) { 
    for (int i = x; i <= n; i += lowbit(i)) { 
        for (int j = y; j <= n; j += lowbit(j)) { 
            a[i][j]++;
        }
    }
}
int sum(int x, int y) { 
    int res = 0;
    for (int i = x; i > 0; i -= lowbit(i)) { 
        for (int j = y; j > 0; j -= lowbit(j))
            res += a[i][j];
    }
    return res;
}
int main() { 
    int ca, t;
    int x, y, u, v;
    scanf("%d", &ca);
    while (ca--) { 
        memset(a, 0, sizeof(a));
        scanf("%d%d", &n, &t);
        while (t--) { 
            scanf("%s%d%d", s, &x, &y);
            if (s[0] == 'C') { 
                scanf("%d%d", &u, &v);
                x++, y++;
                u++, v++;
                update(u, v);
                update(x - 1, y - 1);
                update(x - 1, v);
                update(u, y - 1);
            }
            else { 
                printf("%d\n", sum(x, y) % 2);
            }
        }
        printf("\n");
    }
    return 0;
}