POJ 2155 Matrix 树状数组

一、题目大意

有一个n*n 全是 0 的矩阵，两种操作

1、区间反转y1行到y2行，x1列到x2列的所有元素。（反转就是1变0，0变1）

2、单点查询(x,y)的值

二、解题思路

提到反转问题，我们就明白只需要记录操作次数即可，最终操作次数如果是奇数就是1，如果是偶数是0。

然后我们设 (x,y)坐标位置这个点反转的次数为 S(y,x)，我们来考虑下当 [y1,y2]行,[x1,x2]列区间反转对于x和y的影响

1、当y

2、当y1<=y<=y2且x1<=x<=x2时，S(y,x)=S(y,x)+1

3、当 y2

4、当 y1<=y<=y2 且 x2

5、当 y2

我们可以定义一个二维数组bit，然后用bit前y列、前x行的和代表S(y,x)

针对第一点，不需要进行操作就可以达到

针对第二点，我们可以将二维bit[y1][x1]+=1，这样当y1<=y且x1<=x时，计算bit前y行和x列的和时就会+1。

针对第三点，我们需要对x1列以后，y2+1行和之后的行进行处理，所以我们可以对bit[y2+1][x1]+=(-1)，这样，计算y2

针对第四点，我们需要对y1行以后，x2+1列和之后的列进行处理，可以bit[y1][x2+1]+=(-1)，这样，计算y1<=y<=y2，x2

针对第5点，考虑到我们之前对bit[y1][x2+1]和bit[y2+1][x]都做了-1处理，如果计算bit的y2

然后再简单说下bit如何扩展到二维的情况，举个例子吧，一维树状数组的第4位，保存的是[1,4]的和，第6位保存的是[5,6]的和（这里是因为6=0110，抽出最左边的1转成10进制是2，所以6管理2个元素，也就是它自己和它前面的一个元素）

如果扩展到二维的情况，那么bit[4][4]就可以管理前4行的[1,4]的和，bit[6][6]就代表着[5,6]区间内的两行的[5,6]区间里元素的值，bit[4][6]代表的是[1,4]区间里行的[5,6]区间里元素的和。bit[6][4]代表的是[5,6]区间里行的[1,4]区间里的元素的和。

那么树状数组更新第i行第j列的单点值增加x时候，只需要根据 i = i + (i&(-i))来操作所有行，然后针对每一行，设k=j按照 k = k + (k&(-k))依次加x。

树状数组计算前i行前j列的区间和的时候，只需要根据 i = i - (i&(-i))来计算节点的所有子行，然后针对每一行，设置k=j，按照 k = k - (k&(-k))依次加上所有子元素即可。

（二维树状数组的话需要创建一个二维数组，然后每次更新和计算下标为i 的 树状数组的下标为k的值）

（每次求和时，每一行的循环加的元素数量是相同的）

然后注意下每次一组样例后，多输出一个\n，不然会报 PE

三、代码

#include 
using namespace std;
int bit[1032][1032], n, n_;
void init()
{
    n = 1;
    while (n < n_)
    {
        n = n * 2;
    }
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            bit[i][j] = 0;
        }
    }
}
void update(int row, int col, int v)
{
    if (row <= 0 || col <= 0)
    {
        return;
    }
    for (int i = row; i <= n; i = i + (i & (-i)))
    {
        for (int j = col; j <= n; j = j + (j & (-j)))
        {
            bit[i][j] = bit[i][j] + v;
        }
    }
}
int query(int row, int col)
{
    int sum = 0;
    for (int i = row; i > 0; i = i - (i & (-i)))
    {
        for (int j = col; j > 0; j = j - (j & (-j)))
        {
            sum = sum + bit[i][j];
        }
    }
    return sum;
}
int main()
{
    int x, x1, y1, x2, y2, t;
    char c;
    scanf("%d", &x);
    while (x--)
    {
        scanf("%d%d", &n_, &t);
        init();
        while (t--)
        {
            scanf("\n%c", &c);
            if (c == 'Q')
            {
                scanf("%d%d", &x1, &y1);
                int result = query(y1, x1);
                if (result & 1)
                {
                    printf("1\n");
                }
                else
                {
                    printf("0\n");
                }
            }
            else if (c == 'C')
            {
                scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
                update(y1, x1, 1);
                update(y1, x2 + 1, -1);
                update(y2 + 1, x1, -1);
                update(y2 + 1, x2 + 1, 1);
            }
        }
        printf("\n");
    }
    return 0;
}