When do we need this data structure？

提前计算一些特定位置 prefix sum 计算一段距离的时候通过Bit来寻找 加入一个元素也是通过Bit （下一个元素是 去除最后一个1得到的 逐渐增加 直到大于长度

• use array of size n+1
• start with 0 array insert each item with add
• range(i , j) = sum(j) - sum(i - 1)

Not for min/max : segment/interval tree

非常好的解释的视频

307. Range Sum Query - Mutable

注意sum函数并不是 prefix数组 需要计算 getSum 下标相减的时候弄清楚

public class NumArray {
    int[] nums;
    int[] bits;
    int length;

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

308. Range Sum Query 2D - Mutable

sum(i , j) 代表从(0,0) 到(i , j) 的面积 则图中阴影的 等于右下角的减去两个边缘的 再加上左上角多剪出来的部分

如果不变的话直接可以用DP做 提前计算好 然后用四角的加减计算 https://leetcode.com/submissions/detail/98445305/

public class NumMatrix {

    public int[][] tree;
    public int[][] nums;
    int m;
    int n;

    public NumMatrix(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return;
        m = matrix.length;
        n = matrix[0].length;
        nums = new int[m][n];
        tree = new int[m+1][n+1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                update(i, j, matrix[i][j]);
            }
        }
    }
    //first we need to insert and update the tree. We are not assigning the nums[][] 2d array right away because
    //we need to update the value. 
    public void update(int row, int col, int val) {
        if (m == 0 || n == 0) return;
        int delta = val - nums[row][col];
        nums[row][col] = val;
        for (int i = row + 1; i <= m; i += i & (-i)) {
            for (int j = col + 1; j <= n; j += j & (-j)) {
                tree[i][j] += delta;
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        if (m == 0 || n == 0) return 0;
        return sum(row2+1, col2+1) + sum(row1, col1) - sum(row1, col2+1) - sum(row2+1, col1);
    }

    public int sum(int row, int col) {
        int sum = 0;
        for (int i = row; i > 0; i -= i & (-i)) {
            for (int j = col; j > 0; j -= j & (-j)) {
                sum += tree[i][j];
            }
        }
        return sum;
    }
}

315. Count of Smaller Numbers After Self

The intuitive binary search tree solution: build the binary search tree from the end of the array to the start of the array. Insert each item by traversing the tree during which count the number of nodes to the left of the current node. In the process append the count to the final result. Finally reverse the result.

493. Reverse Pairs

There is a good explanation of these kinds of array problem but I didn't start to digest it yet