Fenwick Tree (Binary Indexed Tree)

给定n个元素array，时间复杂度为

• build O(n log n)
• update O(log n)
• query O(log n)

space complexity would be O(n)

Fenwick Tree主要用于求各种维度的区间sum，主要缺点在于 建树时间长于segment tree，需要O(n log n)时间，还有和面 试官解释的时候比较麻烦。。主要优点是好写，而且非常容易扩 展到多维情况。

motivation: given a 1D array of n elements, naive implementation for query and update, or we can use DP to pre-compute the prefix sums in O(n), but what if the values of elements can change? Fenwick tree was proposed to solve the prefix sum problem. The idea is to store partial sum in each node and get total sum by traversing the tree from leaf to root. The tree has a height of log(n)

Range Sum Query - Mutable

class NumArray {
    int[] fenwickTree;
    int length;
    int[] arr;

    public NumArray(int[] nums) {
        length = nums.length;
        arr = new int[length];
        fenwickTree = new int[length + 1];

        for (int i = 0; i < length; i++) {
            update(i, nums[i]);
        }
    }

    public void update(int i, int val) {
        int diff = val - arr[i];
        arr[i] = val;
        for (int index = i + 1; index <= length; index += (index & -index)) {
            fenwickTree[index] += diff;
        }
    }

    public int sumRange(int i, int j) {
        return getSum(j + 1) - getSum(i);
    }

    private int getSum(int i) {
        int sum = 0;
        while (i > 0) {
            sum += fenwickTree[i];
            i -= (i & -i);
        }
        return sum;
    }
}

Range Sum Query 2D - Mutable

note: 增加维度的逻辑非常简单，只需要把对应的tree array增加维度就可以了，这时候 新的getSum(i,j)所代表的是，从(0,0)开始到(i,j)的矩形范围内的sum，相对于一 维fenwick tree中的(0, index)的和。

• fenwick tree本质上是树状的prefix sum数组，维度非常灵活，每一个位置上的getSum()都代表当前坐标到origin原点 cumulative sum.
• 因此对于矩阵中任意矩形，都可以看做四个以原点为起点的矩形的相互覆盖，可以以同样的时间复杂度求解矩阵中任意位置任意形状的矩形和。

class NumMatrix {

    int[][] fenwickTree;
    int[][] arr;
    int rows;
    int cols;

    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return;

        rows = matrix.length;
        cols = matrix[0].length;

        fenwickTree = new int[rows + 1][cols + 1];
        arr = new int[rows][cols];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                update(i, j, matrix[i][j]);
            }
        }
    }

    public void update(int row, int col, int val) {
        int diff = val - arr[row][col];
        arr[row][col] = val;
        for (int i = row + 1; i <= rows; i+= (i & -i)) {
            for (int j = col + 1; j <= cols; j += (j & -j)) {
                fenwickTree[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 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 += fenwickTree[i][j];
            }
        }
        return sum;
    }
}

refer: http://www.hawstein.com/posts/binary-indexed-trees.html

https://www.youtube.com/watch?v=CWDQJGaN1gY

Range Sum Query 2D - Immutable

note:

class NumMatrix {
    int[][] arr;
    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return;
        int n = matrix.length;
        int m = matrix[0].length;
        arr = new int[n + 1][m + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i + 1][j + 1] = arr[i][j + 1] + arr[i + 1][j] - arr[i][j] + matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return arr[row2 + 1][col2 + 1] - arr[row2 + 1][col1] - arr[row1][col2 + 1] + arr[row1][col1];
    }
}

https://leetcode.com/problems/range-sum-query-2d-immutable/solution/