POJ 1195 Mobile Phones：二維樹狀數組（Binary Indexed Tree 2D）

題目

S×S 矩陣 (S ≤ 1024)，支持單點增值（指令 1）和子矩陣求和查詢（指令 2）。指令數 ≤ 60002。輸入以 3 結束測試用例。

二維 BIT 原理

一維 BIT 的二維推廣。update(x,y,val)：沿 x 方向低位增長，內層沿 y 方向低位增長。query(x,y)：沿 x 方向低位減小，內層沿 y 方向低位減小，累加。矩陣區間和利用容斥：sum(x1,y1,x2,y2) = q(x2,y2)-q(x1-1,y2)-q(x2,y1-1)+q(x1-1,y1-1)。座標從 1 開始（輸入 0-based 需 +1），避免 lowbit(0) 死循環。數組大小開 >1024（如 2000）。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2000;
int bit[MAXN][MAXN];

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

void update(int x, int y, int val) {
    for (int i = x; i < MAXN; i += lowbit(i))
        for (int j = y; j < MAXN; j += lowbit(j))
            bit[i][j] += val;
}

int query(int x, int y) {
    int res = 0;
    for (int i = x; i > 0; i -= lowbit(i))
        for (int j = y; j > 0; j -= lowbit(j))
            res += bit[i][j];
    return res;
}

int main() {
    int S;
    while (scanf("%d", &S) == 1) {
        memset(bit, 0, sizeof(bit));
        while (true) {
            int cmd; scanf("%d", &cmd);
            if (cmd == 3) break;
            if (cmd == 1) {
                int x, y, a; scanf("%d%d%d", &x, &y, &a);
                update(x+1, y+1, a);
            } else if (cmd == 2) {
                int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
                x1++; y1++; x2++; y2++;
                int ans = query(x2, y2) - query(x1-1, y2) - query(x2, y1-1) + query(x1-1, y1-1);
                printf("%d\n", ans);
            }
        }
    }
    return 0;
}