Poj 1159 Mobile phones 题解
本题是二维树状数组的典型应用：
代码：
#include <stdio.h>#include <stdlib.h>#include <string.h>using namespace std;int c[1030][1030];int order;int s;int lowbit(int t){ return t&(-t);}void update(int x,int y,int a){ while(x<=s) { int tempy = y; while(tempy<=s) { c[x][tempy]+=a; tempy+=lowbit(tempy); } x+=lowbit(x); }}int getSum(int x,int y){ int sum = 0; while(x>0) { int tempy = y; while(tempy>0) { sum+=c[x][tempy]; tempy-=lowbit(tempy); } x-=lowbit(x); } return sum;}int main(){ scanf("%d",&order); while(order<3) { if(order == 0) { scanf("%d",&s); memset(c,0,sizeof(c)); } else if(order == 1) { int x,y,a; scanf("%d%d%d",&x,&y,&a); update(x+1,y+1,a); } else if(order == 2) { int x1,x2,y1,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); printf("%d\n",getSum(x2+1,y2+1)-getSum(x1,y2+1)-getSum(x2+1,y1)+getSum(x1,y1)); } scanf("%d",&order); } return 0;}