二叉索引树

概述和用途

二叉索引树（Binary Index Tree 简称BIT）又称树状数组或者Fenwick树，最早由Peter M. Fenwick与1994年发表。其初衷是解决数据压缩离的累积率（Cumulative Frequency）的计算问题，现在多用于高效计算数列的前缀和，区间和。构建BIT的时间复杂度为O（NlogN），空间复杂度为O（N）。搜索和更新的复杂度为O（logN）

含义

假设有一个数组a[i]，长度为N，数组的每个元素存储着一个数字。

image.png

由于某种原因，我们需要得到一个新的数组sum[i]，sum[i]数组中的每个元素都是数组a[i]中相应元素的前缀和，换句话说，sum[i]的值等于从a[0]到a[i]的累加和，表示成公式就是：
sum[i] = ∑a[j], 0<=j<=i。

image.png
sum[i]检索起来非常方便，时间复杂度为O(1)，但是问题是如果a[i]会频繁的进行更新，那么相应的sum[i]数组也必须随之更新，每次更新的时间复杂度为O(N)，特别是在N相当大的情况下，程序的效率将急剧下降。

因此必须找到一个更好的方法来解决效率的问题。建立一个树，

1. 树的根节点index为0，是一个dummy节点，并不存储任何信息。这个树有7个节点，index为1～7，分别对应原数组a[i]的元素0～6也就是说树的总节点数比原数组a[i]的元素个数大一。

2. 注意到每一个节点和他的子节点有着一致的对应关系。

例如：
节点1，用二进制表示：01，如果将最后一位1移除，则得到00
节点2，用二进制表示：10，如果将最后一位1移除，则得到00
节点4，用二进制表示：100，如果将最后一位1移除，则得到00
而他们的父节点0，用二进制表示：00

再看：
节点5，用二进制表示：101，如果将最后一位1移除，则得到100
节点6，用二进制表示：110，如果将最后一位1移除，则得到100
而他们的父节点4，用二进制表示：100

3. 对于每个节点，其index都可以表示成2ⁱ¹+2ⁱ²+…+2ⁱⁿ的形式。例如：

1 = 0 + 2^0
2 = 0 + 2^1
4 = 0 + 2^2
5 = 2^2 + 2^0
6 = 2^2 + 2^1
7 = 2^2 + 2^1 + 2^0

根据这一规律，计算每个节点存储的值。

节点1: a[0] 
节点2: a[0] + a[1]
节点4: a[0] + a[1] + a[2] + a[3]
节点5: a[4]
节点6: a[4] + a[5]
节点7: a[6] 

通过以上步骤，我们建立起了一个BIT:

image.png

利用BIT计算前缀和

现在，考虑如取得想要的前缀和，对于树中的任意一个节点，将其表示为T[i]，1<=i<=7，

sum[4] = T[5] + T[4] = 16
sum[6] = T[7] + T[6] + T[4] = 2 + 4 +11 = 17

也就是说，只需从树上对应的节点，回溯至跟节点，并将路径上所有节点的数值累加，即可得到前缀和。时间复杂度为O(logN)。如果一时想不通为什么，可以试着考虑节点右上角（start，end）的含义，即每个节点代表了数组上某一跨度范围内的元素的累加和。

用算法构建和更新BIT

接下来，考虑用算法构建和更新这个树。

对于构建来说，插入节点的过程就是不断更新树的过程，所以首先考虑更新树。每更新一个节点，则只需更新其后的兄弟节点，以及其所有祖先节点之后的所有兄弟节点。
假设我们需要更新a[2]的值，需更新T[3]和T[4]的值；如果需要更新a[4]的值，则需更新T[5]和T[6]的值。也就是说，如果更新a[i] 的值，则应该更新T[j1] ，T[j2]，… T[jk]的值。其中，j1 = i + m1，m1是这样得到的：

1. 将i表示为二进制，取从低位开始第一个不为0的位，假设为b1
2. m1= 2 ^(b1-1)

j2 = j1 + m2,
1.将j1表示为二进制，取从低位开始第一个不为0的位，假设为b2，
2.m2= 2 ^(b2-1)

以此类推，直到jk+1 > N。

我知道看到这里，你可能会有两种反应：
1.大脑有些缺氧。
2.王之蔑视。
的确，熟悉C语言的同学应该已经想起简洁明了的位运算了：

nextPos = currentPos + （currentPos & -currentPos）

写成代码：

    private static int[] buildBIT(int[] origin){

        int[] bitArray = new int[origin.length + 1];

        for(int i = 0; i<bitArray.length; i++){
            bitArray[i] = 0;
        }

        for(int i = 1; i< bitArray.length; i++){
            updateBitArray(origin[i-1], i, bitArray);
        }

        return bitArray;
    }

    private static void updateBitArray(int valueDelta, int bitArrayPos, int[] bitArray){

        bitArray[bitArrayPos] += valueDelta;

        // get next position in bit array, change it
        int next = getNext(bitArrayPos);
        while(next < bitArray.length){
            bitArray[next] += valueDelta;
            next = getNext(next);
        }
    }

    private static int getNext(int cur){
        return cur + (cur & -cur);
    }

时间复杂度ON(logN)，空间复杂度O(N)。

用算法计算前缀和

最后，来看如何对树进行检索，也就是说，给定一个i，求sum[i] = ∑a[j], 0<=j<=i。

根据前面的说明，不难得知，只需要找到节点T[i+1]，回溯至跟节点，并将路径上所有节点的数值累加，即可得到前缀和。这里同样要借助位运算：

parentPos = currentPos -（currentPos & -currentPos）

写成代码：

    private static int searchSum(int[] bitArray, int cur){
        int sum = bitArray[cur];
        int parent = getParent(cur);
        while(parent > 0){
            sum += bitArray[parent];
            parent = getParent(parent);
        }
        return sum;
    }

时间复杂度O(logN)，空间复杂度O(1)。

树状数组
Tushar Roy 小哥的专栏