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;
}