POJ 1195 Mobile phones (二维树状数组)

浏览数：25 / 时间：2015年06月08日

题意：在一个S*S的正方形内，有两种操作　
1　X Y A 是在（X,Y）这个点加A

2 X1 Y1 X2 Y2 查询（X1,X2) 到 (Y1,Y2) 这个矩形范围内手机的数量

而且数据的边界也是从0开始用树状数组的时候要加一处理

对于求矩形面积用一个大的矩形剪去三个边界的小矩形即可

ans=query(x2,y2)-query(x2,y1-1)-query(x1-1,y2)+query(x1-1,y1-1);

//4352K	547MS
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define M 1050
int tree[M][M],lim;

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

void add(int x,int y,int val)
{
    int tmp;
    while(x<=lim){
        tmp=y;
        while(tmp<=lim){
            tree[x][tmp]+=val;
            tmp+=lowbit(tmp);
        }
        x+=lowbit(x);
    }
}
int query(int x,int y)
{
    int s=0;
    while(x>0){
        int tmp=y;
        while(tmp>0){
            s+=tree[x][tmp];
            tmp-=lowbit(tmp);
        }
        x-=lowbit(x);
    }
    return s;
}

int main()
{
    int op;
    while(scanf("%d",&op)&&op!=3){
        if(op==0){
            scanf("%d",&lim);
            lim++;
        }
        if(op==1){
            int a,b,val;
            scanf("%d%d%d",&a,&b,&val);
            add(a+1,b+1,val);
        }
        if(op==2){
            int x1,y1,x2,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            x1++;
            y1++;
            x2++;
            y2++;
            int ans=query(x2,y2)-query(x2,y1-1)-query(x1-1,y2)+query(x1-1,y1-1);
            printf("%d\n",ans);
        }

    }
    return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

POJ 1195 Mobile phones (二维树状数组)