> For the complete documentation index, see [llms.txt](https://mnunknown.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mnunknown.gitbook.io/algorithm-notes/segment_and_fenwick_tree/66-_tree-_fenwick_tree_binary_indexed_tree.md).

# 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 [视频讲解](https://www.youtube.com/watch?v=CWDQJGaN1gY)

### [binary index tree](https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/#2d) ，另一个教程贴在[这里](http://cs.stackexchange.com/questions/10538/bit-what-is-the-intuition-behind-a-binary-indexed-tree-and-how-was-it-thought-a)，还有[这里](https://sanugupta.wordpress.com/2014/08/29/binary-indexed-tree-fenwick-tree/)，加上这个陈老师推荐的[中文帖子](http://www.hawstein.com/posts/binary-indexed-trees.html)

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](https://leetcode.com/problems/range-sum-query-mutable/)

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

### [图文并茂的视频讲解\~ ](https://www.youtube.com/watch?v=v_wj_mOAlig)

![](/files/-MUt7aaOgfqqm9jzzgzt)

![](/files/-MUt7aaPLTlPoo3qe79F)

![](/files/-MUt7aaQw27AhKAdy_H4)

> * **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] 的过程

```java
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](https://leetcode.com/problems/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.**
* **因此对于矩阵中任意矩形，都可以看做四个以原点为起点的矩形的相互覆盖，可以以同样的时间复杂度求解矩阵中任意位置任意形状的矩形和。**

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