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

题目链接:http://poj.org/problem?id=1195

题意是有四种操作。

当n==0时:输入一个m表示初始化矩阵(m*m且值都为0)。

当n==1时:输入x,y,z,表示(x,y)点加上z。

当n==2时:输入x,y,z,d,输出坐标(x,y)到坐标(z,d)的总和。

当n==3时:结束输入。

二维树状数组的入门模板题了,其实二维和一维的差不多,一维的理解了,二维的看着代码想一下就差不多了。


AC代码:

#include <iostreaM>
#include <cstdio>
#include <cstring>
#define maxn 2005
using namespace std;
int pre[maxn][maxn];
int n,m,x,z,y,d;

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

void Add(int x,int y,int z){
    for(int i=x;i<=m;i+=lowbit(i)){
        for(int j=y;j<=m;j+=lowbit(j)){
            pre[i][j] += z;
        }
    }
}

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

int main()
{
    while(~scanf("%d",&n)){
        if(n == 3)break;
        if(n == 0){
            scanf("%d",&m);
            for(int i=1;i<=m;i++){
                for(int j=1;j<=m;j++){
                    pre[i][j] = 0;
                }
            }
        }
        if(n == 1){
            scanf("%d%d%d",&x,&y,&z);
            x++;y++;
            Add(x,y,z);
        }
        if(n == 2){
            scanf("%d%d%d%d",&x,&y,&z,&d);
            x++;y++;z++;d++;
            printf("%d\n",Query(z, d)-Query(x-1, d)-Query(z, y-1)+Query(x-1, y-1));
        }
    }
    return 0;
}

本文同步分享在 博客“Ch_zaqdt”(CSDN)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

评论

暂无评论