poj 2155 matrix

彻底弄懂二维树状数组

http://www.java3z.com/cwbwebhome/article/article1/1369.html?id=4804

09年国家集训队武森《浅谈信息学竞赛中的“0” 和“ 1”》的论文

http://wenku.baidu.com/link?url=Nl7I-GFx9wN1SiHSmOT9RDQ-1Aesr3aAhKImIzlsLqSI7ZCfQcwmWjO_IYN1-j6D2WRluAkQRywTJdJvS1UAgusX8JdhKDtBEM5ovpM9Cxy

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #define N 1002
 5 using namespace std;
 6 int g[N][N];
 7 
 8 inline int lowbit(int x)
 9 {
10     return x&-x;
11 }
12 
13 void add(int x,int y)
14 {
15     int i,j;
16     for(i=x;i<N;i+=lowbit(i))
17         for(j=y;j<N;j+=lowbit(j))
18             g[i][j]++;
19 }
20 
21 int sum(int x,int y)
22 {
23     int i,j,res=0;
24     for(i=x;i>0;i-=lowbit(i))
25         for(j=y;j>0;j-=lowbit(j))
26             res+=g[i][j];
27     return res;
28 }
29 
30 void run()
31 {
32     int n,_;
33     int x1,x2,y1,y2;
34     char c;
35     scanf("%d%d",&n,&_);
36     memset(g,0,sizeof(g));
37     while(_--)
38     {
39         scanf("%c%c",&c,&c);
40         if(c=='C')
41         {
42             scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
43             add(x1,y1);
44             add(x2+1,y1);
45             add(x1,y2+1);
46             add(x2+1,y2+1);
47         }
48         else
49         {
50             scanf("%d%d",&x1,&y1);
51             printf("%d
",sum(x1,y1)%2);
52         }
53     }
54     cout<<endl;
55 }
56 
57 int main()
58 {
59     int _;
60     scanf("%d",&_);
61     while(_--)
62         run();
63     return 0;
64 }