問題描述

S×S 矩陣（S≤1024），初始全 0。操作：

1. 1 x y a：mat[x][y] += a（a 可負，保證不低於 0）。
2. 2 x1 y1 x2 y2：查詢子矩陣 [x1,y1, x2,y2] 元素和。
3. 3：結束。

指令數 ≤ 60002，需高效支持單點更新、區間查詢。

二維樹狀數組

bit[x][y] 維護 (1,1) 到 (x,y) 的前綴和。
更新：for(i=x; i<=S; i+=lowbit(i)) for(j=y; j<=S; j+=lowbit(j)) bit[i][j] += v;
查詢前綴和：for(i=x; i>0; i-=lowbit(i)) for(j=y; j>0; j-=lowbit(j)) res += bit[i][j];
區間和：sum(x2,y2) - sum(x1-1,y2) - sum(x2,y1-1) + sum(x1-1,y1-1)。

代碼實現

#include <cstdio>
#include <cstring>
const int MAXS = 1025;
int bit[MAXS][MAXS];
int S;

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

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

int sum(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 op;
    scanf("%d%d", &op, &S); // 首行：指令碼 0 和 S
    while (~scanf("%d", &op)) {
        if (op == 3) break;
        if (op == 1) {
            int x, y, a; scanf("%d%d%d", &x, &y, &a);
            add(x+1, y+1, a); // 0-based -> 1-based
        } else if (op == 2) {
            int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            ++x1; ++y1; ++x2; ++y2;
            int ans = sum(x2,y2) - sum(x1-1,y2) - sum(x2,y1-1) + sum(x1-1,y1-1);
            printf("%d\n", ans);
        }
    }
    return 0;
}

關鍵細節

1. 座標轉換：題目 0-based，BIT 1-based，所有座標 +1。
2. 矩陣大小：S≤1024，BIT 開 [1025][1025] 足夠（索引 1~1024）。
3. 輸入格式：首行兩數（指令碼 0 和 S），後續每行一指令。用 while(~scanf("%d",&op)) 讀取。
4. 長整型：單元格值 ≤ 32767，總和 ≤ 2^31，int 足夠；若 S=1024 全滿 32767，總和 ≈ 3.4e10 需 long long。建議 BIT 用 long long。
5. 指令 0 忽略：首行指令碼 0 不處理，直接讀 S。

複雜度

• 單次更新/查詢：O(log² S) ≈ 10×10 = 100 操作。
• 60000 指令 ≈ 600 萬操作，極快。
• 空間：O(S²) ≈ 4MB（int）或 8MB（long long）。

總結

POJ 1195 是二維樹狀數組的經典模板題。核心是將二維前綴和分解為兩層一維 BIT 循環，座標 0-based 轉 1-based，區間和用容斥原理。注意：首行指令碼 0 為干擾項，實際操作從第二行開始。掌握二維 BIT 模板，所有「二維單點更新、區間查詢」問題通用。