程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> POJ 2155 Matrix 二維樹狀數組

POJ 2155 Matrix 二維樹狀數組

編輯:關於C++

 

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

要注意的是,這裡數組必須重新定義,不能是默認定義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;
    }
}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved