运用树状数组解决动态数组求和

摘要：对于一组一维数组解决前项和，如果使用的方法需要的时间来找到前项数字的和，但是可以用的时间来更新对应数字的值但是仍然需要的时间来更新牵扯到相应数字数组的和，相反可以使用树状数组来降低运行时间求数组内一段数组的和，但同样我们增加了更新树状数组内

对于一组一维数组解决前n项和，如果使用linear scan的方法, 需要O(n)的时间来找到前n项数字的和，但是可以用O(1)的时间来更新对应数字的值,但是仍然需要Linear的时间来更新牵扯到相应数字数组的和，相反可以使用树状数组来降低运行时间求数组内一段数组的和，但同样我们增加了更新树状数组内任意节点数值的时间。
树状数组(Binary Indexed Tree)中每个节点的值是原数组中一个或几个数组的和，所以在原数组中进行求和操作就是在树状数组中进行节点的求和操作, 相对应的时间复杂度为O(logN)

Binary Index Tree 基于二进制编码建立:

需要保持一个原始数组a[], 和新建立一个树状数组e[],相对应的二进制编码：

1 : 1     a[1]
2 : 10    e[2] = e[1] + a[2];
3 : 011   e[3] = a[3];
4 : 110   e[4] = e[2] + e[3] + a[4];
5 : 101   e[5] = a[5];
6 : 110   e[6] = e[5] + e[6];
7 : 111   e[7] = a[7];
8 : 1000  e[8] = e[4] + e[6] + e[7] + a[8];
e[4] = a[1] + a[2] + a[3] + a[4];

如果二进制表示中末尾有连续的0，则e[i]是原数组中2^k数值的和
因此可以通过计算e[i]的前驱和后继节点来计算出相对应e[i]的值，实现方法：
lowBit = (i & (-i))
因此，我们有一个数组：

int[] nums;
public int[] NumArray(int[] nums) {
    this.nums = nums;
    //Binary Indexed Trees
    int[] tree = new int[nums.length + 1];
    for(int i = 0; i < tree.length; i++) {
        sum = 0;
        lowBit = i & (-i);
        for(int j = i; i > i - lowBit; j--) {
            sum += sum + nums[j - i];
        }
        tree[i] = sum;
}
public void update(int i, int val) {
    //更新差值，从后往前相加
    int diff = val - nums[i];
    nums[i] = val;
    i++;
    for(; i < tree.length; i++) {
        tree[i] += diff;
    }
}
public void sumRange(int i, int j) {
    return sum(i + j) - sum(i);
}
private int sumRange(int i, int j) {
    int sum = 0;
    for(int i = k; i > 0; i -= i & (-i)) {
        sum += tree[i];
    }
    return sum;
}

Binary Index Tree 主要运用是 Range Sum with Mutable Elements:

Range Sum with Mutable Elements 1D
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

class Solution{
    int[] nums;
    int[] tree;
    int size;
    
    //time: O(nlogn)
    public RangeSumQueryMutable(int[] nums) {
        this.size = nums.length;
        this.tree = new int[size + 1];
        this.nums = new int[size];
    
        for(int i = 0; i < n; i++) {
            updateTree(i, nums[i]);
        }
   }
   
   public void updateTree(int i, int val) {
       i = i + 1;
       while(i < size) {
           tree[i] += val;
           i += i & (-i); //the last set bits, 2s compliment
       }
   }
   
   public void update(int i, int val) {
       if(size == 0) return;
       update(i, val - nums[i]);
       nums[i] = val;
   }
   
   public int sumRange(int i, int j) {
       if(i == 0) return j;
       return getSum(j) - getSum(i - 1);     
   }
   
   private void getSum(int i) {
      int sum = 0;
      i = i + 1;
      while(i > 0) {
          sum += tree[i];
          i -= i & (-i);//go to ancestor
      }
      return sum;
   }

Range Sum with Mutable Elements 2D
Given matrix =

  [[3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]]

sumRegion(2, 1, 4, 3) -> 8
update(3, 2, 2)
sumRegion(2, 1, 4, 3) -> 10

class Solution {
    int[][] nums;
    int[][] tree;
    int rows;
    int cols;
    public class RangeSum2D(int[][] nums) {
        rows = nums.length;
        cols = nums[0].length;
        nums = new int[rows][cols];
        tree = new int[rows + 1][cols + 1];
        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                update(nums[i][j], i, j);
            }
        }
    }
    public void update(int val, int row, int col) {
        int diff = val - nums[i][j];
        nums[row][col] = val;
        for(int i = row + 1; i < rows; i += (i & (-i))) {
            for(int j = col + 1; i < cols; j += (j & (-j))) {
                tree[i][j] += diff;
            }
        }
    }
   public int sumRegion(int row1, int col1, int row2, int col2) {
        return getSum(row2 + 1, col2 + 1) + getSum(row1, col1) - getSum(row1, col2 + 1) - getSum(row2 + 1, col1);
   }

    private int getSum(int i, int j) {
        int sum = 0;
        for(int i = rows; i > 0; i -= (i & (-i))) {
            for(int j = cols; j > 0; j -= (j & (-j)) {
                sum += tree[i][j];
            }
        }
        return sum;
    }
    //O(m * logn * n * logn)