首页 > 代码库 > 二维树状数组（水题） POJ1195
二维树状数组（水题） POJ1195
前段时间遇到线段树过不了，树状数组却过了的题。（其实线段树过得了的）
回忆了下树状数组。
主要原理，还是二进制位数，每一项的和表示其为它的前（（最后一位1及其后）的二进制数）和，可从二进制图来看。（用线段树想一想其实只是线段树编号不同而已，本质类似）
写了下二维树状数组，几乎和一维相同，也没必要不同。
#include <cstdio>#include <cstring>int l,r,x,y,n,a,p,sum[1125][1125];inline int lowbit(int x){ return x&(-x);}void update(int x, int y, int p){ for(int i=x; i<=n; i+=lowbit(i)) for(int j=y; j<=n; j+=lowbit(j)) sum[i][j]+=p;}int query(int x, int y){ int ret=0; for(int i=x; i>0; i-=lowbit(i)) for(int j=y; j>0; j-=lowbit(j)) ret+=sum[i][j]; return ret;}int main(){ while(scanf("%d",&p)!=EOF) { if(p==3) break; switch (p) { case 0: memset(sum,0,sizeof(sum)); scanf("%d",&n); break; case 1: scanf("%d%d%d",&x,&y,&a); update(x+1,y+1,a); break; case 2: scanf("%d%d%d%d",&x,&y,&l,&r); printf("%d\n",query(l+1,r+1)-query(l+1,y)-query(x,r+1)+query(x,y)); break; } } return 0;}
二维树状数组（水题） POJ1195
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。