2019-08-19 区域检索

1. Range Sum Query - Immutable——1维范围搜索——不可变——动态规划
   题目：Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
   Example:
   Given nums = [-2, 0, 3, -5, 2, -1]
   sumRange(0, 2) -> 1
   sumRange(2, 5) -> -1
   sumRange(0, 5) -> -3

    int[] nums ;
    public NumArray(int[] nums) {
        for(int i = 1; i<nums.length; i++){
            nums[i] = nums[i] + nums[i-1];
        }
        this.nums = nums;
    }
    
    public int sumRange(int i, int j) {
        if(i==0)
            return this.nums[j];
        return this.nums[j]-nums[i-1];
    }

2. Range Sum Query 2D - Immutable——2位范围搜索——不可变——动态规划
   题目：Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
   题目与上题类似，就是换成二维了

    int[][] dp;
    
    public NumMatrix(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return;
        
        int m=matrix.length,n=matrix[0].length;
        dp = new int[m+1][n+1];
        
        for(int i=1; i<=m;i++){
            for(int j =1; j <= n; j++){
                dp[i][j] = dp[i][j-1] + dp[i-1][j]-dp[i-1][j-1]+matrix[i-1][j-1];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int x_max = Math.max(row1, row2);
        int x_min = Math.min(row1, row2);
        int y_max = Math.max(col1, col2);
        int y_min = Math.min(col1, col2);
        
        return dp[x_max+1][y_max+1]-dp[x_max+1][y_min]-dp[x_min][y_max+1]+dp[x_min][y_min];
    }

3. Range Sum Query - Mutable——树状数组
   树状数组：是一种查询和修改复杂度均为 O(logn) 的数据结构。这个树状数组比较有意思，所有的奇数位置的数字和原数组对应位置的相同，偶数位置是前面几个位置之和
   题目：Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
   The update(i, val) function modifies nums by updating the element at index i to val.
   Example:
   Given nums = [1, 3, 5]
   sumRange(0, 2) -> 9
   update(1, 2)
   sumRange(0, 2) -> 8
   分析：那么是如何确定某个位置到底是有几个数组成的呢，原来是根据坐标的最低位 Low Bit 来决定的，所谓的最低位，就是二进制数的最右边的一个1开始，加上后面的0(如果有的话)组成的数字，例如1到8的最低位如下面所示：
   坐标 二进制 最低位
   1 0001 1
   2 0010 2
   3 0011 1
   4 0100 4
   5 0101 1
   6 0110 2
   7 0111 1
   8 1000 8
   ...
   最低位的计算方法有两种，一种是 x&(x^(x–1))，另一种是利用补码特性 x&-x。
   首先从头到尾遍历一次数组，求出每个位置的树状数组bit[]。
   若当前位置=j，则下一个包含j运算的位置是：j+=j&(-j)
   若当前位置=j，则从index=0到j的总和sum=bit[j] + bit[j-=j&(-j)] + bit[j-=j&(-j)]

class NumArray {

    int[] nums;
    int[] bits;
    public NumArray(int[] nums) {
        this.nums = new int[nums.length];
        bits = new int[nums.length+1];
        for(int i=0;i<nums.length;i++){
            update(i,nums[i]);
        }
    }
    
    public void update(int i, int val) {
        int diff = val-nums[i];
        for(int j=i+1;j<bits.length;j+=(j&-j)){
            bits[j]+=diff;
        }
        nums[i]=val;
    }
    
    public int sumRange(int i, int j) {
        return getSum(j+1)-getSum(i);
    }
    
    public int getSum(int i){
        int sum = 0;
        for(int j=i;j>0;j-=(j&-j)){
            sum += bits[j];
        }
        return sum;
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */