首页 > 代码库 > poj2155 Matrix 【二维树状数组】
poj2155 Matrix 【二维树状数组】
有工具在手,这题就是一个模板题,就是有点不清楚,最后问的是单个元素的值,它怎么sum求出来的
#include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> using namespace std; #define maxn 1005 int c[maxn][maxn]; int Row, Col; inline int Lowbit(const int &x) { return x & (-x); } int Sum(int i, int j) { int tempj, sum = 0; while (i > 0) { tempj = j; while (tempj > 0) { sum += c[i][tempj]; tempj -= Lowbit(tempj); } i -= Lowbit(i); } return sum; } void Update(int i, int j, int num) { int tempj; while (i <= Row) { tempj = j; while (tempj <= Col) { c[i][tempj] += num; tempj += Lowbit(tempj); } i += Lowbit(i); } } int main() { #ifndef ONLINE_JUDGE freopen("G:/1.txt","r",stdin); freopen("G:/2.txt","w",stdout); #endif int T; scanf("%d",&T); while(T--) { memset(c,0,sizeof(c)); int N,Q;scanf("%d%d",&N,&Q);getchar(); Row=N;Col=N; for(int i=1;i<=Q;i++) { char ques;int a,b,c,d; scanf("%c ",&ques);//getchar(); if(ques=='C') { scanf("%d%d%d%d",&a,&b,&c,&d);getchar(); c++;d++; Update(a,b,1); Update(c,d,1); Update(c,b,-1); Update(a,d,-1); } else if(ques=='Q') { scanf("%d%d",&a,&b);getchar(); printf("%d\n",1&Sum(a,b)); } } printf("\n"); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。