POJ 1195 Mobile Phones

树状数组，开始的时候wa了，后来看看，原来是概率论没学好，以为求(L,B) - (R,T) 矩阵内的和只要用sum(R+1,T+1) - sum(L,B) 就行了，。傻x了。。

必须 sum(R,T) - sum(L,T) - sum(R,B) + sum(L,B) ;  (R,T 已经自加1)   诫之。

 

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 1027

int c[N][N];
int n;

int lowbit(int x)
{
    return x&(-x);
}

void modify(int x,int y,int val)
{
    for(int i=x;i<=n;i+=lowbit(i))
    {
        for(int j=y;j<=n;j+=lowbit(j))
        {
            c[i][j] += val;
        }
    }
}

int sum(int x,int y)
{
    int res = 0;
    for(int i=x;i>0;i-=lowbit(i))
    {
        for(int j=y;j>0;j-=lowbit(j))
        {
            res += c[i][j];
        }
    }
    return res;
}

int main()
{
    int op,L,B,R,T,A,X,Y;
    while(scanf("%d",&op)!=EOF)
    {
        if(op == 3)
            break;
        else if(op == 0)
        {
            memset(c,0,sizeof(c));
            scanf("%d",&n);
        }
        else if(op == 1)
        {
            scanf("%d%d%d",&X,&Y,&A);
            X++;Y++;
            modify(X,Y,A);
        }
        else if(op == 2)
        {
            scanf("%d%d%d%d",&L,&B,&R,&T);
            R++;T++;
            printf("%d
",sum(R,T)-sum(L,T)-sum(R,B)+sum(L,B));
        }
    }
    return 0;
}