POJ 1195 Mobile phones（二维树状数组）

点我看题目

题意： 4条命令，0代表开始，在整组样例里肯定只有第一条是0，0后边的数字代表的矩阵的大小为n*n，1 x y z代表着将z加到（x，y）这个格子上去，2 l b r t代表着，让你求出从（l，b）到（b，r）所包含的矩形中包含的移动电话的数量。

思路：当时看书的时候我就看到二维数组了，一看这个题我就想到了用二维，二维其实和一维差不多，这个就是个模板题。不过依然要注意的是树状数组是从1开始的，所以输入之后要+1以防从0开始。

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

const int maxn = 4123 ;
int tree[1100][1100] ;
int n ;

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

void update(int i,int j,int k)
{
    while(i <= n)
    {
        int temp = j ;
        while(temp <= n)
        {
            tree[i][temp] += k ;
            temp += lowbit(temp) ;
        }
        i += lowbit(i) ;
    }
}

int sum(int i,int j)
{
    int sum1 = 0;
    while(i > 0)
    {
        int temp = j ;
        while(temp > 0)
        {
            sum1 += tree[i][temp] ;
            temp -= lowbit(temp) ;
        }
        i -= lowbit(i) ;
    }
    return sum1 ;
}

int main()
{
    int n1 ;
    int l,b,r,t ;
    memset(tree,0,sizeof(tree)) ;
    while(scanf("%d",&n1) && n1 < 3)
    {
        if(n1 == 0)
            scanf("%d",&n) ;
        else if(n1 == 1)
        {
            scanf("%d %d %d",&l,&b,&r) ;
            l++;
            b++ ;
            update(l,b,r) ;
        }
        else if(n1 == 2)
        {
            scanf("%d %d %d %d",&l,&b,&r,&t) ;
            l++ ;
            b++ ;
            r++ ;
            t++ ;
            int s = sum(r,t)-sum(l-1,t)-sum(r,b-1)+sum(l-1,b-1) ;
            printf("%d
",s) ;
        }
    }
    return 0;
}

View Code

POJ 1195 Mobile phones（二维树状数组）

相关推荐