首页 > 代码库 > poj2155Matrix【二位树状数组】
poj2155Matrix【二位树状数组】
大意：告诉你一个矩阵，初始值全部为0，有两种操作，1、告诉你x1，y1， x2， y2 把左上角到右下角的矩形的里面的值全部颠倒 1变0 0变1
第二种操作是查询某个点的值是0或1
分析：二维的标号法， 对于每一个矩阵只要把它的四个角进行标记就可以了， 最基本的思路跟理工门前的树是一样的
举个例子：
比如告诉你左上角（x1， y1） 右下角（x2， y2）
那么对于这个矩形 我们只要把（x1， y1），（x1 + 1， y2），（x2 + 1， y1），（x2 + 1， y2 + 1）标记上
那么对于每次查询的话该位置的值就是从该位置到（1， 1）这个矩阵之内的所有的数的和
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 const int maxn = 1005; 7 8 int lowbit(int x) { 9 return x & ( - x );10 }11 12 int c[maxn][maxn];13 int n;14 15 void add(int i, int j, int value) {16 int xx = j;17 while(i <= n) {18 j = xx;19 while(j <= n) {20 c[i][j] += value;21 j += lowbit(j);22 }23 i += lowbit(i);24 }25 }26 27 int Sum(int i, int j) {28 int xx = j;29 int sum = 0;30 while(i > 0) {31 j = xx;32 while(j > 0) {33 sum += c[i][j];34 j -= lowbit(j);35 }36 i -= lowbit(i);37 }38 return sum;39 }40 41 int main() {42 int t;43 int m;44 char cc;45 int x1, y1, x2, y2;46 bool flag = false;47 scanf("%d",&t);48 while(t--) {49 if(flag) puts("");50 flag = true;51 scanf("%d %d",&n, &m);52 memset(c, 0, sizeof(c));53 for(int i = 1; i <= m; i++) {54 scanf("\n%c %d %d", &cc, &x1, &y1);55 if(cc == ‘C‘) {56 scanf("%d %d",&x2, &y2);57 add(x1, y1, 1);58 add(x1, y2 + 1, 1);59 add(x2 + 1, y1, 1);60 add(x2 + 1, y2 + 1, 1);61 } else {62 printf("%d\n", Sum(x1, y1) % 2 );63 }64 }65 }66 return 0;67 }68
poj2155Matrix【二位树状数组】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。