摘要：對于一組一維數組解決前項和，如果使用的方法需要的時間來找到前項數字的和，但是可以用的時間來更新對應數字的值但是仍然需要的時間來更新牽扯到相應數字數組的和，相反可以使用樹狀數組來降低運行時間求數組內一段數組的和，但同樣我們增加了更新樹狀數組內

對于一組一維數組解決前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)