xindoo is
always here

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


       由于英语极差,看了半天也没看懂题目,最后参考了其他人的题解才搞懂题目,我就直接把题意贴过来了 

     

题意:这道题目只是题意自己就去理解了半天,大概题意如下:给出i一个n*n的矩阵,初始化为均为0,还有关于这个矩阵的几种操作,操作如下:命令1:(X Y A)对位于坐标(X Y)的值加A;命令2:(L B R T)求出位于L<=x<=R,B<=y<=T的值的和;命令3:退出不做任何操作。

 

思路分析如下:二维树状数组,典型的动态操作题目。查询子矩阵(x,y,xx,yy)的元素和,注意一下就可以了:sum(xx, yy)-sum(x-1, yy)-sum(xx, y-1)+sum(x-1,y-1);

      这是我做的第一道二维树状树组的题目,感觉和一维的差不多,下面是题解。

 

//poj 1195
#include <stdio.h>
#include <string.h>
const int maxn = 1030;

int n, a[maxn][maxn];

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

void update(int i, int j, int v)
{
    int t;
     while(i <= n)
     {
         t = j;                        //不能改变j的值,因为每次循环都要用到
         while (t <= n)
         {
             a[i][t] += v;
             t += lowbit(t);
         }
         i += lowbit(i);
     }
}

int getsum(int i, int j)
{
    int sum = 0, t;
    while (i > 0)
    {
        t = j;                          //不能改变j的值,因为每次循环都要用到
        while (t > 0)
        {
            sum += a[i][t];
            t -= lowbit(t);
        }
        i -= lowbit(i);
    }
    return sum;
}

int main()
{
    int op, x, y, v, xx, yy;
    while (scanf("%d%d",&op,&n) != EOF)
    {
        memset(a, 0, sizeof(a));
        while (scanf("%d",&op) && op != 3)
        {
            if (op == 1)
            {
                scanf("%d%d%d",&x, &y, &v);
                x++; y++;                         //树状数组坐标是从1开始的,以此要加1
                update(x, y, v);
            }
            else
            {
                scanf("%d%d%d%d", &x, &y, &xx, &yy);
                x ++, y ++, xx ++, yy ++;
                int ans = getsum(xx, yy) - getsum(x-1, yy) - getsum(xx, y-1) + getsum(x-1, y-1);
                // 每次getsum(i, j); 得到的结果是(i,j)前面所有数的和 
                printf("%d\n", ans);
            }
        }
    }
    return 0;
}


 

  


打赏
未经允许不得转载:XINDOO » POJ 1195 Mobile phones (二维树状树组)
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏