二维树状数组（poj 1195）

题目：http://poj.org/PRoblem?id=1195

题意：

题解：利用二维树状数组，利用logn复杂度对一个点进行更新，再利用logn复杂度践行查找，题目就很简单了

代码：

#include<cstdio>#include<cstdio>#include<cstring>#include<string>#include<algorithm>using namespace std;int c[1500][1500];int MAXN=1025;//树状数组常用的东西，不加多说int lowbit(int x){    return x & (-x);}//注意 该更新是二维更新，复杂度logn × lognint add(int x,int y,int val){    for(int i=x;i<=MAXN;i+=lowbit(i))    {        for(int j=y;j<=MAXN;j+=lowbit(j))        {            c[i][j]+=val;        }    }}//求和操作int sum(int x,int y){    int sum=0;    for(int i=x;i>0;i-=lowbit(i))    {        for(int j=y;j>0;j-=lowbit(j))        {            sum+=c[i][j];        }    }    return sum;}int main(){    int l,r;    scanf("%d %d",&l,&r);    MAXN=r;    int q;    while(~scanf("%d",&q) && q!=3)    {        if(q==1)        {            int x,y,val;            scanf("%d %d %d",&x,&y,&val);            x++;y++;            add(x,y,val);        }        else if(q==2)        {            int l1,l2,r1,r2;            scanf("%d%d%d%d",&x,&y,&l1,&r1);            x++;            y++;            l1++;            r1++;            printf("%d/n",sum(l1,r1)-sum(l1,y-1)-sum(x-1,r1)+sum(x-1,y-1));        }    }    return 0;}