前段时间遇到线段树过不了，树状数组却过了的题。（其实线段树过得了的）
回忆了下树状数组。
主要原理，还是二进制位数，每一项的和表示其为它的前（（最后一位1及其后）的二进制数）和，可从二进制图来看。（用线段树想一想其实只是线段树编号不同而已，本质类似）
写了下二维树状数组，几乎和一维相同，也没必要不同。
#include <cstdio>
#include <cstring> int l,r,x,y,n,a,p,sum[][]; 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=;
for(int i=x; i>; i-=lowbit(i))
for(int j=y; j>; j-=lowbit(j))
ret+=sum[i][j];
return ret;
} int main()
{
while(scanf("%d",&p)!=EOF)
{
if(p==) break;
switch (p) {
case :
memset(sum,,sizeof(sum));
scanf("%d",&n);
break;
case :
scanf("%d%d%d",&x,&y,&a);
update(x+,y+,a);
break;
case :
scanf("%d%d%d%d",&x,&y,&l,&r);
printf("%d\n",query(l+,r+)-query(l+,y)-query(x,r+)+query(x,y));
break;
}
}
return ;
}