POJ 2155 Matrix：二維樹狀數組實現區間翻轉與單點查詢

問題描述

N×N 矩陣初始全 0。兩類操作：
• C x1 y1 x2 y2：子矩陣 (x1,y1) 到 (x2,y2) 所有元素翻轉 (0↔1)
• Q x y：查詢 (x,y) 當前值
N ≤ 1000，T ≤ 50000，多測試用例。

核心技巧：二維差分 + 模 2

翻轉操作等價於區間加 1 (模 2)。二維差分數組 bit (Binary Indexed Tree / Fenwick Tree) 支持：
• 區間加：add(x1,y1,1); add(x1,y2+1,-1); add(x2+1,y1,-1); add(x2+1,y2+1,1)
• 單點查：sum(x,y) 返回 (1,1) 到 (x,y) 前綴和，模 2 即值

二維 BIT 模板

const int MAXN = 1005;
int bit[MAXN][MAXN], n;

void add(int x, int y, int val) {
    for (int i = x; i > 0; i -= i & -i)
        for (int j = y; j > 0; j -= j & -j)
            bit[i][j] += val;
}

int sum(int x, int y) {
    int s = 0;
    for (int i = x; i <= n; i += i & -i)
        for (int j = y; j <= n; j += j & -j)
            s += bit[i][j];
    return s;
}

注意：此處 add 走 i -= lowbit，sum 走 i += lowbit，是「改段求點」模式 (區間更新、單點查詢)。

操作映射

C x1 y1 x2 y2：
add(x2, y2, 1);
add(x1-1, y2, -1);
add(x2, y1-1, -1);
add(x1-1, y1-1, 1);

Q x y：
printf("%d\n", sum(x, y) % 2);

完整代碼

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1005;
int bit[N][N], n;

void add(int x, int y, int v) {
    for (int i = x; i > 0; i -= i & -i)
        for (int j = y; j > 0; j -= j & -j)
            bit[i][j] += v;
}

int sum(int x, int y) {
    int s = 0;
    for (int i = x; i <= n; i += i & -i)
        for (int j = y; j <= n; j += j & -j)
            s += bit[i][j];
    return s;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int q; scanf("%d%d", &n, &q);
        memset(bit, 0, sizeof(bit));
        while (q--) {
            char op[2]; scanf("%s", op);
            if (op[0] == 'C') {
                int x1,y1,x2,y2; scanf("%d%d%d%d", &x1,&y1,&x2,&y2);
                add(x2, y2, 1);
                add(x1-1, y2, -1);
                add(x2, y1-1, -1);
                add(x1-1, y1-1, 1);
            } else {
                int x,y; scanf("%d%d", &x,&y);
                printf("%d\n", sum(x,y) & 1);
            }
        }
        puts(""); // 測試用例間空行
    }
    return 0;
}

複雜度

• 單次操作：O(log²N) ≈ 100 步
• 總操作：50000 × 100 = 5e6，極快
• 空間：O(N²) = 1e6 int ≈ 4MB

關鍵理解

一維「改段求點」 BIT 邏輯：
維護差分數組 B[i] = A[i] - A[i-1]。
區間 [l,r] 加 c → B[l]+=c, B[r+1]-=c。
單點查 A[x] = Σ_{i=1}^x B[i] (前綴和)。
二維同理，bit 存儲二維差分，sum(x,y) 計算二維前綴和。