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

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

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.

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).
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

Sample Output

题解：

题目意思就是给一个大小为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，因为这里的区间更新比较特殊，所以查询的时候每一点的值要把前面的区间值全部加上。。。感觉我说了我自己都不太懂，就这样吧

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

这个博客的图对这题的理解很有帮助，二维中，假如图是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;
}