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;}