poj 2155 Matrix (二维树状数组)

        这是楼教主出的二维线段树或者是二维树状数组的题，题意很简单，就是有个n*n的矩阵，初始值都是0，然后给你两个操作，一个是给你左上角和右下角的坐标，把这个长方形的区间所有元素反取反（0变1 1变0），另一个是求某个具体坐标的值。

       这里我用了二维的线树状数组，一维树状数组可以解决区间更新和点查询的问题，这里只需要加一维就可以了，代码比较好写，不过开始犯了很多低级的错误。

  

   

    

     

    
    

     

      //============================================================================
     
    
   

    

     

    
    

     

      // Name : 2012083101.cpp
     
    
   

    

     

    
    

     

      // Author : xindoo
     
    
   

    

     

    
    

     

      // Version :
     
    
   

    

     

    
    

     

      // Copyright : Your copyright notice
     
    
   

    

     

    
    

     

      // Description : poj 2155
     
    
   

    

     

    
    

     

      // Data : 2013-08-29-17.06
     
    
   

    

     

    
    

     

      //============================================================================
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      #include <string.h>
     
    
   

    

     

    
    

     

      const int maxn = 1004;
     
    
   

    

     

    
    

     

      int xy[maxn][maxn];
     
    
   

    

     

    
    

     

      int n;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      inline int lowbit(int x)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    return x&-x;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void update(int x, int y, int v)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int t = y;
     
    
   

    

     

    
    

     
    while (x <= n)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

          	y = t;
     
    
   

    

     

    
    

     
        while (y <= n)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     

                  xy[x][y] += v;
     
    
   

    

     

    
    

     

                  y += lowbit(y);
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

              x += lowbit(x);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int getsum(int x, int y)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    int sum = 0;
     
    
   

    

     

    
    

     
    int t = y;
     
    
   

    

     

    
    

     
    while (x)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

          	y = t;
     
    
   

    

     

    
    

     
        while (y)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     

                  sum += xy[x][y];
     
    
   

    

     

    
    

     

                  y -= lowbit(y);
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

              x -= lowbit(x);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    return sum;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    int q, kase;
     
    
   

    

     

    
    

     
    char op;
     
    
   

    

     

    
    

     
    int x1, x2, y1, y2;
     
    
   

    

     

    
    

     
    scanf("%d", &kase);
     
    
   

    

     

    
    

     
    while (kase--)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     
        scanf("%d %d", &n, &q);
     
    
   

    

     

    
    

     
        memset(xy, 0, sizeof(xy));
     
    
   

    

     

    
    

     
        while (q--)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     
            getchar();
     
    
   

    

     

    
    

     
            scanf("%c", &op);
     
    
   

    

     

    
    

     
            if (op == 'Q')
     
    
   

    

     

    
    

     

                  {
     
    
   

    

     

    
    

     
                scanf("%d %d", &x1, &y1);
     
    
   

    

     

    
    

     
                int t = getsum(x1, y1);
     
    
   

    

     

    
    

     
                if (t&1)
     
    
   

    

     

    
    

     
                    printf("%d\n", 1);
     
    
   

    

     

    
    

     
                else
     
    
   

    

     

    
    

     
                    printf("%d\n", 0);
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     
            else
     
    
   

    

     

    
    

     

                  {
     
    
   

    

     

    
    

     
                scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
     
    
   

    

     

    
    

     
                update(x1, y1, 1);
     
    
   

    

     

    
    

     
                update(x1, y2+1, -1);
     
    
   

    

     

    
    

     
                update(x2+1, y1, -1);
     
    
   

    

     

    
    

     
                update(x2+1, y2+1, 1);
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        if (kase)
     
    
   

    

     

    
    

     
            puts("");
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: xindoo.blog.csdn.net，作者：xindoo，版权归原作者所有，如需转载，请联系作者。

原文链接：xindoo.blog.csdn.net/article/details/10737545