POJ 2155 Matrix（二维树状数组+数组数组区间更新+单点查询）

柔光的暖阳◎ 2022-06-11 00:26 139阅读 0赞

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.  
  
The first line of each block contains two numbers N and T (2 <= N <= 1000, 1 <= T <= 50000) representing the size of the matrix and the number of the instructions. The following T lines each represents an instruction having the format "Q x y" or "C x1 y1 x2 y2", which has been described above.

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

1
    2 10
    C 2 1 2 2
    Q 2 2
    C 2 1 2 1
    Q 1 1
    C 1 1 2 1
    C 1 2 1 2
    C 1 1 2 2
    Q 1 1
    C 1 1 2 1
    Q 2 1

Sample Output

1
    0
    0
    1

题解：

题目意思就是给一个大小为n\*n的二维矩阵，一开始全部是0，然后操作数是t，如果输出字符为"Q"就是询问矩阵x，y位置的值，为"C"，然后输出两个点坐标，表示矩阵的左上角和右下角坐标，在这些矩阵里面的值取反。。不知道用线段树怎么做，后来看一篇二维树状数组的博客看懂了。

首先写出这题你要会树状数组的区间更新，没错树状数组也可以区间更新，原理不太清楚qaq我就先讲一下做法，就是假如要在一个区间x,y上加上一个值v，那么就在数组sum\[x\]处加上v，在sum\[y+1\]处减去v，区间更新就完成了，不同的是当查询单点处x的情况的时候，单点的值是sum\[1\]+...+sum\[x\]，累加起来就是单点处的值了。

如何说说我的理解：

在sum\[x\]处加上v，因为更新是往后更新的（每次加上x&（-x）），所以这时后面的区间每个都多了个v，然后再sum\[y+1\]处减去v，就相当于把区间外多加上的v去掉，这就完成了\[x,y\]内加上v，因为这里的区间更新比较特殊，所以查询的时候每一点的值要把前面的区间值全部加上。。。感觉我说了我自己都不太懂，就这样吧

然后因为讲解这题要画图感受，所以我就直接贴我看过的博客好了[点击打开链接][Link 1]

这个博客的图对这题的理解很有帮助，二维中，假如图是n\*n的，如果在\[x,y\]处加了v就相当于以左上角坐标\[x，y\]，到右下角坐标\[n\*n\]的大矩形里面全部值加上了v，然后后续操作就是修剪加多了的地方，加上剪多了的地方最后就完成了更新

代码：

#include<iostream>
    #include<stdio.h>
    #include<map>
    #include<algorithm>
    #include<math.h>
    #include<queue>
    #include<stack>
    #include<string>
    #include<cstring>
    using namespace std;
    int sum[1005][1005];
    int n;
    int lowbit(int x)
    {
        return x&(-x);
    }
    int getsum(int x,int y)
    {
        int s=0;
        while(x>0)
        {
            int t=y;
            while(t>0)//二维需要理解
            {
                s+=sum[x][t];
                t-=lowbit(t);
            }
            x-=lowbit(x);
        }
        return s%2;//精髓
    }
    void update(int x,int y,int v)
    {
        while(x<=n)//与查询差不多
        {
            int t=y;
            while(t<=n)
            {
                sum[x][t]+=v;
                t+=lowbit(t);
            }
            x+=lowbit(x);
        }
    }
    int main()
    {
        int i,j,test,m,x1,y1,x2,y2,x,y;
        char c;
        scanf("%d",&test);
        while(test--)
        {
            memset(sum,0,sizeof(sum));//要初始化
            scanf("%d%d",&n,&m);
            for(i=0;i<m;i++)
            {
                getchar();//吸收回车
                scanf("%c",&c);
                if(c=='C')
                {
                    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                    update(x1,y1,1);//往大矩形里加上了1
                    update(x2+1,y1,-1);
                    update(x1,y2+1,-1);//修剪这个大矩形
                    update(x2+1,y2+1,1);//加上多剪了的
                }
                else
                {
                    scanf("%d%d",&x,&y);
                    printf("%d\n",getsum(x,y));
                }
            }
            if(test)
                printf("\n");
        }
        return 0;
    }

[Link 1]: http://blog.csdn.net/acm_BaiHuzi/article/details/46819049