Fenwick Tree (Binary Indexed Tree)

陈老师说花三天时间研究明白这个没啥意义。不过我看了小半天就看完了。。也没啥难的嘛。。。

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

• build O(n log n)

• update O(log n)

• query O(log n)

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

Youtube视频讲解

binary index tree，另一个教程贴在这里，还有这里，加上这个陈老师推荐的中文帖子

The two's complement of an N-bit number is defined as the complement with respect to 2^N; in other words, it is the result of subtracting the number from 2^N

Range Sum Query - Mutable

和之前那道题一样，把 segment tree 改成 fenwick tree 的写法如下：

图文并茂的视频讲解~

• fenwick tree 可以用 array 存，纯靠 bit manipulation 操作。

• tree 有一个 dummy root，所以对于单维度大小为 n 的输入，实际数组会在每一个维度 +1 的 padding.

• 因此在每次更新原数组 index 位置的数时，在树上实际的 update 位置是 index + 1.

• 树的 update 过程很像机器学习里面的 forward/backward propagation，每次更新之后先计算 diff，再把 diff 传导过去。因此 fenwick tree 有时候需要一个数组去保存所有值，用于计算 diff.

• 对于给定 index，树的 update 是一个 index 逐渐增加的过程，相对的，树的求和是个不断寻找 parent，index 逐渐减小的过程。

在图上的树状结构中，任意一个点的 parent 等于其 binary representation 的最右一个 1 的 bit 上再 +1; 比如 3 = 0011 ，parent = 8 = 0100.

从 child 到 parent 这条线，代表着更新。上图的结构，也是相对于更新操作的 tree structure.

而 query 是另一种结构和搜索过程，是一步一步把 index 的 binary representation 拆出来，变成 13 = 001011 ，对应 BIT[001000] + BIT[000010] + BIT[000001] 的过程

public 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]);
        }
    }

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

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

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

Range Sum Query 2D - Mutable

Fenwick Tree 在增加维度上的优势在这题中体现的非常好。

这题如果 int[][] nums 直接指向 matrix 会在 update 操作之后得到错误结果，目前我还没仔细想为什么。。。稳妥起见还是老老实实新建一个吧。

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

• fenwick tree 本质上是树状的 prefix sum 数组，维度非常灵活，每一个位置上的getSum()都代表当前坐标到 origin 原点的 cumulative sum.

• 因此对于矩阵中任意矩形，都可以看做四个以原点为起点的矩形的相互覆盖，可以以同样的时间复杂度求解矩阵中任意位置任意形状的矩形和。

public class NumMatrix {
    int[][] fenwickTree;
    int[][] nums;
    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];
        nums = 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 - nums[row][col];
        nums[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;
            }
        }
    }

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

    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);
    }
}