0%

POJ1195-Mobile phones

发表于 更新于

题目链接

题目概述

有S*S台基站排列成正方形，每台基站都会记录连接它的手机数，并且该数目随时可能变化。要求输出指定矩形区域内连接手机的总数。

题目分析

由于 S 很大，矩形区域也可能很大，使用双重循环来计算总数会超市，所以需要一种特殊的数据结构：二维树状数组。与一维树状数组原理相同，假设二维数组为：

1
2
3
4
5
a[][]={
	{a11,a12,a13,a14,a15,a16,a17,a18},
	{a21,a22,a23,a24,a25,a26,a27,a28},
	{a31,a32,a33,a34,a35,a36,a37,a38},
	{a41,a42,a43,a44,a45,a46,a47,a48}};

那么树状数组C：

1
2
3
4
C[1][1]=a11, C[1][2]=a11+a12;
C[2][1]=a11+a21, C[2][2]=a11+a12+a21+a22;
C[3][1]=a31, C[3][2]=a31+a32;
C[4][1]=a11+a21+a31+a41, C[4][2]=a11+a12+a21+a22+a31+a32+a41+a42；

可以看出，不管是每一行还是每一列，树状数组C都符合x+=lowbit(x)，所以只需要按下图所示的顺序进行一维的add，就能实现二维树状数组的add。

IMG_0076

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstdio>
#include <iostream>
using namespace std;

const int MAXN=1025;
int tree[MAXN][MAXN];
int s;
#define lowbit(x) x&-(x)
void add(int x, int y, int d){
    int i=x, j=y;
    while(j<=s){
        i=x;
        while(i<=s){
            tree[j][i]+=d;
            i+=lowbit(i);
        }
        j+=lowbit(j);
    }
}
int getsum(int x, int y){
    int sum=0;
    for(int i=y; i>0; i-=lowbit(i))
        for(int j=x; j>0; j-=lowbit(j))
            sum+=tree[i][j];

    return sum;
}

int main(){
    scanf("%d%d", &s, &s);
    int ins=0,x,y,a,l,b,r,t;
    scanf("%d", &ins);
    while(ins!=3){
        switch(ins){
            case 1: //add
                scanf("%d%d%d", &x, &y, &a);
                x++,y++;
                add(x, y, a);
                break;
            case 2:
                scanf("%d%d%d%d", &l, &b, &r, &t);
                l++,r++,b++,t++; //⚠️注意，这里要++，因为输入的坐标可能为0
                printf("%d\n", getsum(r,t)-getsum(l-1,t)-getsum(r,b-1)+getsum(l-1,b-1)); //⚠️注意，部分地方要-1
                break;
        }
        scanf("%d", &ins);
    }
    return 0;
}

自我总结

需要注意的点已经在代码中标注出来，还是要牢记，树状数组的下标从1开始，这一点千万不能忘记。在计算区域和的时候也要注意，getsum(r,t)-getsum(l-1,t)-getsum(r,b-1)+getsum(l-1,b-1)，哪里要减1哪里不需要，要想明白。