学步园

题意：给出一个S * S的矩阵，每个位置可以放手机，初始时每个位置的都是空的。现要执行一些操作：1 X Y A，在位置(X, Y)增加A台手机，2 L B R T，查询(L, B)到(R, T)的矩阵的手机有多少（0 <= X, Y < S, 1 <= S <= 1024, -32768 <= A <= 32767, 手机总和最多只有2^30台）。

题目链接：http://poj.org/problem?id=1195

——>>二维树状数组模板题。。。设c[x][y]表示[x - lowerbit(x) + 1, x], [y - lowerbit(y) + 1, y]的所有点的手机总台数。于是……#^_^

#include <cstdio>
#include <cstring>

using namespace std;

const int maxs = 1024 + 10;

int S;
int c[maxs][maxs];

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

void add(int x, int y, int v) {
    for(int i = x; i <= S; i += lowerbit(i))
        for(int j = y; j <= S; j += lowerbit(j))
            c[i][j] += v;
}

int sum(int x, int y) {
    int ret = 0;
    for(int i = x; i > 0; i -= lowerbit(i))
        for(int j = y; j > 0; j -= lowerbit(j))
            ret += c[i][j];
    return ret;
}

int main()
{
    int instraction, X, Y, A, L, B, R, T;
    while(scanf("%d", &instraction) == 1) {
        switch(instraction) {
        case 0: {
            scanf("%d", &S);
            S++;
            memset(c, 0, sizeof(c));
            break;
        }
        case 1: {
            scanf("%d%d%d", &X, &Y, &A);
            add(X+1, Y+1, A);
            break;
        }
        case 2: {
            scanf("%d%d%d%d", &L, &B, &R, &T);
            L++;
            B++;
            R++;
            T++;
            printf("%d\n", sum(R, T) - sum(R, B-1) - sum(L-1, T) + sum(L-1, B-1));
            break;
        }
        default: break;
        }
    }
    return 0;
}