Fenwick Tree (Binary Indexed Tree)

PreviousSegment Tree 的应用 NextRange Sum Query 2D - Immutable

Last updated 4 years ago

Was this helpful?

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

，另一个教程贴在，还有，加上这个陈老师推荐的

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

和之前那道题一样，把 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);
    }
}

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