• poj 2155 Matrix 二维树状数组


    二维树状数组 ,其实与一维树状数组没有太大区别。具体参考博客:https://www.cnblogs.com/RabbitHu/p/BIT.html

    代码如下:

     1 /*
     2 poj 2155 Matrix  
     3   二维树状数组 
     4 */
     5 #include <iostream>
     6 #include <cstring>
     7 #include <stdio.h>
     8 using namespace std;
     9 #define MAX 1001
    10 #define lowbit(x)  (x & (-x))
    11 using namespace std;
    12 int n,q;
    13 int c[MAX][MAX];
    14 
    15 void update(int x,int y,int val)
    16 {
    17    for (int i=x;i<=n;i+=lowbit(i))
    18     for(int j=y;j<=n;j+=lowbit(j))
    19        c[i][j]+=val;
    20 }
    21 
    22 int getsum(int x,int y)
    23 {
    24       int ans = 0;
    25   for (int i=x;i;i-=lowbit(i))
    26     for(int j=y;j;j-=lowbit(j))
    27        ans+=c[i][j];
    28     return ans;
    29 }
    30 
    31 int main ()
    32 {
    33   int T;
    34   int x1,y1,x2,y2; 
    35   cin >>T;
    36   char ch;
    37  while(T--)
    38  {
    39    scanf ("%d%d",&n,&q);
    40    memset(c,0,sizeof(c));
    41    for (int i=0;i<q;++i)
    42     {
    43         cin >>ch;  
    44        if (ch == 'Q')//查询 
    45          {
    46              scanf ("%d%d",&x1,&y1);
    47              printf ("%d
    ",(getsum(x1,y1))%2);
    48          }
    49        else   //更新 
    50        {
    51             scanf ("%d%d%d%d",&x1,&y1,&x2,&y2);
    52          update(x1,y1,1);
    53          update(x2+1,y1,-1); 
    54          update(x1,y2+1,-1);
    55          update(x2+1,y2+1,1);/*
    56           具体还是差分。区间的修改 
    57          假如图是n*n的,如果在[x,y]处加了v就相当于以左上角坐标[x,y],
    58          到右下角坐标[n*n]的大矩形里面全部值加上了v,
    59          然后后续操作就是修剪加多了的地方,加
    60          上剪多了的地方最后就完成了更新*/ 
    61            
    62        }
    63       
    64     }
    65      printf ("
    ");
    66  }
    67   return 0;
    68 }
    69 /*
    70 1
    71 2 10
    72 C 2 1 2 2
    73 Q 2 3
    74 C 2 1 2 1
    75 Q 1 1
    76 C 1 1 2 1
    77 C 1 2 1 2
    78 C 1 1 2 2
    79 Q 1 1
    80 C 1 1 2 1
    81 Q 2 1
    82 
    83 
    84 */
  • 相关阅读:
    假期python复习2
    假期python复习
    java学习博客2
    Ubuntu20.04安装配置java和tomcat部署静态html网站方法
    如何使用eclipse使用Maven
    __block用结构体使用forwarding指针的原因
    Block存储域学习
    Block捕获__block局部变量的底层原理
    《Objective-C 高级编程》 1.2.3节 alloc/retain/release/dealloc 实现——学习总结
    UICollectonView使用总结
  • 原文地址:https://www.cnblogs.com/yuluoluo/p/8671586.html
一二三 - 开发者的网上家园