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

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