Binary Index Tree

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

0 引言

Leetcode307

这道题给一个可变数组，求从\(i\)到\(j\)的元素之和。

一个naive的做法是，每次查询都从\(i\)累加到\(j\)：

class NumArray {

public:

    NumArray(vector<int>& nums) {

        nums_ = nums;

    }

    void update(int i, int val) {

        nums_[i] = val;

    }

    int sumRange(int i, int j) {

        int ans = 0;

        for(int l = i;l <= j;++l)

            ans += nums_[l];

        return ans;

    }

private:

    vector<int> nums_;

};

这种方法每次更新的复杂度为\(O(1)\)， 每次查询 的复杂度为\(O(n)\)。

1 树状数组

为了降低查询的复杂度，引入Binary Index Tree(Fenwick Tree)：

BIT其实并不是树，而是维护了一个前缀和数组 prefixSums_ ：

假设有一个数组：

那么我们的tree：

0是dummy node，将结点的二进制表示的最后一个1翻转，就能得到其父结点。

下来填充这棵树：

\(1=0+2^0\)，存储从下标0开始的前1个数的和：3（0，0）；

\(2=0+2^1\)，存储从下标0开始的前2个数的和：5（0，1）；

\(3=2^1+2^0\)，存储从下标2开始的前1个数的和：-1（2，2）；

\(4=0+2^2\)，存储从下标0开始的前4个数的和：10（0，3）；

\(5=2^2+2^0\)，存储从下标4开始的前1个数的和：5（4，4）；

\(6=2^2+2^1\)，存储从下标4开始的前2个数的和：9（4，5）；

\(7=2^2+2^1+2^0\)，存储从下标6开始的前1个数的和：-3（6，6）；

\(8=0+2^3\)，存储从下标0开始的前8个数的和：19（0，7）；

\(9=2^3+2^0\)，存储从下标8开始的前1个数的和：7（8，8）；

\(10=2^3+2^1\)，存储从下标8开始的前2个数的和：9（8，9）；

\(11=2^3+2^1+2^0\)，存储从下标10开始的前1个数的和：3（10，10）；

填充后的tree：

接下来就可以根据这棵树来计算 prefixSums_ ：

假如要计算\(0-5\)的和，从下标6出发，一直加到dummy node，得到 prefixSums_[6]=9+10=19 ；

要计算\(0-9\)的和，从下标10出发，一直加到dummy node，得到 prefixSums_[10]=9+19=28 。

以计算\(0-9\)的和为例，结点10存储的是（8，9）的 部分和 ，结点8存储的是（0，7）的 部分和 ，所以加起来就是\(0-9\)的和。

2 快速实现

上面求结点的父结点、将下标拆解为二进制去填充树的方式很慢，来看一种稍快的方式。

查询时，我们需要计算从某结点到dummy node的和，这就涉及计算该结点的parent：

假如要求结点7的parent，7的二进制原码为 111 ，-7的补码为 001 ，将原码和补码按位与得 001 ，用原码减去 001 ，得 110=6 ，即7的父结点是6。

更新时，我们需要更新所有包含该结点的部分和结点：

假如更新了结点1，1的二进制原码为 001 ，-1的补码为 111 ，将原码和补码按位与得 001 ，用原码加上 001 ，得 010=2 ，即还要更新结点2，更新了结点2，还要更新结点4......

最后来看下非常简洁的实现：

class BIT{

private:

    vector<int> prefixSums_;

    static inline int lowbit(int x) {

        return x & (-x);

    }

public:

   BIT(int n) : prefixSums_(n + 1, 0) {}

   void update(int i, int delta) {

        while(i < prefixSums_.size()) {

            prefixSums_[i] += delta;

            i += lowbit(i);

        }

   }

   int query(int i) {

        int sum = 0;

        while(i > 0) {

            sum += prefixSums_[i];

            i -= lowbit(i);

        }

        return sum;

   }

};