摘要：對(duì)于一組一維數(shù)組解決前項(xiàng)和，如果使用的方法需要的時(shí)間來(lái)找到前項(xiàng)數(shù)字的和，但是可以用的時(shí)間來(lái)更新對(duì)應(yīng)數(shù)字的值但是仍然需要的時(shí)間來(lái)更新?tīng)砍兜较鄳?yīng)數(shù)字?jǐn)?shù)組的和，相反可以使用樹(shù)狀數(shù)組來(lái)降低運(yùn)行時(shí)間求數(shù)組內(nèi)一段數(shù)組的和，但同樣我們?cè)黾恿烁聵?shù)狀數(shù)組內(nèi)

對(duì)于一組一維數(shù)組解決前n項(xiàng)和，如果使用linear scan的方法, 需要O(n)的時(shí)間來(lái)找到前n項(xiàng)數(shù)字的和，但是可以用O(1)的時(shí)間來(lái)更新對(duì)應(yīng)數(shù)字的值,但是仍然需要Linear的時(shí)間來(lái)更新?tīng)砍兜较鄳?yīng)數(shù)字?jǐn)?shù)組的和，相反可以使用樹(shù)狀數(shù)組來(lái)降低運(yùn)行時(shí)間求數(shù)組內(nèi)一段數(shù)組的和，但同樣我們?cè)黾恿烁聵?shù)狀數(shù)組內(nèi)任意節(jié)點(diǎn)數(shù)值的時(shí)間。
樹(shù)狀數(shù)組(Binary Indexed Tree)中每個(gè)節(jié)點(diǎn)的值是原數(shù)組中一個(gè)或幾個(gè)數(shù)組的和，所以在原數(shù)組中進(jìn)行求和操作就是在樹(shù)狀數(shù)組中進(jìn)行節(jié)點(diǎn)的求和操作, 相對(duì)應(yīng)的時(shí)間復(fù)雜度為O(logN)

Binary Index Tree 基于二進(jìn)制編碼建立:

需要保持一個(gè)原始數(shù)組a[], 和新建立一個(gè)樹(shù)狀數(shù)組e[],相對(duì)應(yīng)的二進(jìn)制編碼：

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];

如果二進(jìn)制表示中末尾有連續(xù)的0，則e[i]是原數(shù)組中2^k數(shù)值的和
因此可以通過(guò)計(jì)算e[i]的前驅(qū)和后繼節(jié)點(diǎn)來(lái)計(jì)算出相對(duì)應(yīng)e[i]的值，實(shí)現(xiàn)方法：
lowBit = (i & (-i))
因此，我們有一個(gè)數(shù)組：

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 主要運(yùn)用是 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)