POJ 2155 Matrix：二維樹狀數組區間修改、單點查詢

題目簡介

N×N 矩陣（N ≤ 1000），初始全 0。操作：

• C x1 y1 x2 y2：子矩陣 [(x1,y1), (x2,y2)] 所有元素翻轉（0↔1）。
• Q x y：查詢 (x,y) 值。

多測試案例，輸出每次查詢結果。

解題思路：二維樹狀數組（差分思想）

將矩陣視為二維差分數組：對區間翻轉，在四個角做標記：

update(x1, y1, +1);
update(x1, y2+1, -1);
update(x2+1, y1, -1);
update(x2+1, y2+1, +1);

查詢 (x,y) 時，計算前綴和 sum(1..x, 1..y)，奇偶性即為值。二維 BIT 支持單點更新、區間查詢，此處利用差分轉為單點更新、單點查詢（前綴和）。所有操作模 2。

代碼實現

import java.util.*;
public class Main {
    static class BIT {
        int[][] a; int n;
        BIT(int n) { this.n = n; a = new int[n+10][n+10]; }
        void update(int x, int y, int val) {
            for (int i = x; i <= n; i += i&-i)
                for (int j = y; j <= n; j += j&-j) {
                    a[i][j] = (a[i][j] + val) & 1; // 模2
                }
        }
        int query(int x, int y) {
            int res = 0;
            for (int i = x; i > 0; i -= i&-i)
                for (int j = y; j > 0; j -= j&-j)
                    res ^= a[i][j]; // 模2加法即異或
            return res;
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for (int cs = 1; cs <= T; cs++) {
            if (cs > 1) System.out.println();
            int n = in.nextInt(), m = in.nextInt();
            BIT bit = new BIT(n);
            for (int i = 0; i < m; i++) {
                char op = in.next().charAt(0);
                if (op == 'C') {
                    int x1=in.nextInt(), y1=in.nextInt(), x2=in.nextInt(), y2=in.nextInt();
                    bit.update(x1, y1, 1);
                    bit.update(x1, y2+1, 1);
                    bit.update(x2+1, y1, 1);
                    bit.update(x2+1, y2+1, 1);
                } else {
                    int x=in.nextInt(), y=in.nextInt();
                    System.out.println(bit.query(x, y));
                }
            }
        }
    }
}

複雜度分析

單次更新/查詢 O(log^2 N)，總時間 O(M log^2 N)，N=1000, M=50000 極快。