POJ 2155 Matrix 二維樹狀數組

POJ 2155 Matrix 二維樹狀數組

二維樹狀數組，是一維的演變版，沒什麼太大改動

要注意的是，這裡數組必須重新定義，不能是默認定義a[i][j]表示a[i][j]的值，否則二維樹狀數組只能做到單點修改，區間查詢，但此題需要區間修改。

所以不妨換定義，定義a[i][j]表示 a[ i1 ] [ j1 ] ( i =< i1 <= n && j <= j1 <= n )所有值之和，那麼修改時，只需將 a [ x1 ][ y1 ] += 1, a [ x1 ][ y2 + 1 ] -= 1; a [ x2 ][ y1 + 1] -= 1; a[ x2 + 1 ][ y2 + 1 ] +=1; 這個操作不是簡單的 +1 -1，而是在二維樹狀數組上進行。

如此，查找時，只需查找 a[x][y] 即可，這也不是簡單的查找a[x][y]，而是在二維樹狀數組上進行。具體看代碼。

二維線段樹個人還不會，一會學學博主的。

My code (Java)

import java.util.*;


public class Main {
    public static void main(String[] agrs){
        Scanner input = new Scanner(System.in);

        int T = input.nextInt();
        int n, m;
        BIT bit;

        for(int kase = 1; kase <= T; kase++){
            if(kase > 1) System.out.println();

            n = input.nextInt(); m = input.nextInt();
            bit = new BIT(n);

            for(int i = 1; i <= m; i++){
                String s = input.next();

                if(s.charAt(0) == 'C'){
                    int x1, y1, x2, y2;
                    x1 = input.nextInt();
                    y1 = input.nextInt();
                    x2 = input.nextInt();
                    y2 = input.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, y;
                    x = input.nextInt();
                    y = input.nextInt();

                    int ans = bit.query(x, y);
                    ans = (ans % 2 + 2) % 2;

                    System.out.println(ans);
                }
            }
        }

        input.close();
    }
}


class BIT{
    int[][] a;
    int n;

    public BIT(int n){
        this.n = n;
        a = new int[n + 10][n + 10];
    }

    public 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] += val;
                a[i][j] = (a[i][j] % 2 + 2) % 2;
            }
        }
    }

    public int query(int x,int y){
        int ans = 0;
        for(int i = x; i > 0; i -= i&-i){
            for(int j = y; j > 0; j -= j&-j){
                ans = (ans + a[i][j]) % 2;
            }
        }
        return ans;
    }
}