详解二叉索引树(Binary Index Tree又名Fenwick Tree)
何为BIT BIT是一种数据结构，名为树其实用数组即可表达。其主要作用是给定了一个数组(或多维数组)，BIT可用来： O(logN)的复杂度计算给定范围的和,也就是求sum(low, high) O(logN)的复杂度更新数组的一个元素 其构造方法巧妙但简单，可谓大道至简。 给定一个数组a[0 ... N-1],长度N。 BIT表示为indexes[0 ... N],长度N+1。indexes[i]=sum(g(i) ... i], g(i)=i-i&(-i)，注意是左开右闭区间。i&(-i)得到的是一个数字的二进制表示中只留下最右的1后的数字，比如12=[1100],则12&(-12)只留下最右的1就成了4=[0100]。 注意到indexes[]从1开始计数，所以始终有indexes[0]=0。为了说明方便，在数组a[]前面添加了个元素0。 看图说话，如此构造后，原数组的和sum[0 ... i]就可以通过把能覆盖range[0 ... i]的indexes[]加起来得到。比如求sum[0 ... 14]，步骤如下，辅以图示。 先加上indexes[14]，覆盖了a[14], a[13]。 14=[1110],最右1留下后是2=[10],减去后得到12,加上indexes[12]。 12=[1100],最右1留下后是4=[100],减去后得到8,加上indexes[8]。 8=[1000],最右1留下后是8=[1000],减去后得到0，结束。 所以何为BIT,其本质是通过原数组构造一个新数组indexes[]，其中每个元素表示原数组中一段连续子数组的和。范围求和就从线性遍历原数组(O(N))，变成了在indexes[]中快速查找(O(logN))能覆盖所求范围的那几个元素。 而更新则是与求和相反的一个过程,原数组一个元素a[i]更新后，首先需要更新indexes[i]，然后要不停向上，更新每个覆盖了a[i]的indexes元素。比如,a[9]=2 -> a[9]=10,则有： 计算一个更新delta, delta=10-2，更新indexes[9]+=delta, 9=[1001],最右1留下后是1=[0001],加上后得到10,更新indexes[10] += delta。 10=[1010],最右1留下后是2=[0010],加上后得到12,更新indexes[12] += delta。 12=[1100],最右1留下后是4=[0100],加上后得到16,更新indexes[16] += delta。 代码如下: class BIT { private int[] indexes; private int[] nums; public BIT(int[] nums) { this.nums = nums; indexes = new int[nums.length + 1]; for (int i = 0; i < nums....