poj 1195 二维树状数组 及二维树状数组模板

2019-04-14 20:10发布

站内文章 / 模拟电子
11659 0 1352
http://poj.org/problem?id=1195 求矩阵和的时候，下标弄错WA了一次... 求矩形(x1,y1) （x2,y2）的sum
|sum=sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1)
二维树状数组讲解：http://blog.csdn.net/u011026968/article/details/38532117 二维树状数组模板：
/*==================================================* | 二维树状数组 | 1、初始化：INIT: c[][]置为0; Row,Col要赋初值 | 数组下标一定要从1开始!!!!!!!!! | 2、sum(i,j) 前i行前j列的和，update(i,j,num) | 将(i,j)加上num | 3、求矩形(x1,y1) （x2,y2）的sum |sum=sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1) |注意Sum和c 必要的时候用long long *==================================================*/ const int N = 10000; int c[N][N]; int Row, Col; inline int Lowbit(const int &x){// x > 0 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); } }
poj 1195 代码 #include #include #include #include #include #include #include #include #include using namespace std; #define ls(rt) rt*2 #define rs(rt) rt*2+1 #define ll long long #define ull unsigned long long #define rep(i,s,e) for(int i=s;i0) { tmpj=j; while(tmpj>0) { ret+=c[i][tmpj]; tmpj-=lowbit(tmpj); } i-=lowbit(i); } return ret; } void update(int i, int j, int v) { int tmpj; while(i<=row) { tmpj=j; while(tmpj<=col) { c[i][tmpj]+=v; tmpj+=lowbit(tmpj); } i+=lowbit(i); } } int main() { //IN("poj1195.txt"); int op,n,x,y,v; int l,b,r,t; while(~scanf("%d%d",&op,&n)) { col=row=n; CL(c,0); while(~scanf("%d",&op)) { if(op == 3)break; if(op == 1) { scanf("%d%d%d",&x,&y,&v); update(x+1,y+1,v); } if(2 == op) { scanf("%d%d%d%d",&l,&b,&r,&t); printf("%lld ",sum(r+1,t+1)+sum(l,b)-sum(l,t+1)-sum(r+1,b)); } } } return 0; }

热门文章