应用场景
定义数组array[n]，求数组array[i]到array[j]的和(部分和)。在这种情况下，用一个简单的遍历可以解决问题，复杂度为O(n)。如果这种操作执行了m次，那么复杂度为O(mn)，而树状数组可以把复杂度降至O(m*logn)，适用于更新少但是部分和操作次数多的场景。
树状数组
树状数组(Binary Indexed Tree)，本质就是一种通过二进制位来维护一个序列前i个和的数据结构，所以在其实更应该直白地翻译为二进制索引树。树状数组的索引都是以1开始，首先看一个例子。
设原始数组为a[8] = {3,4,5,6,7,8,9,2}，那么树状数组e可以通过如下方式得到：
e[1] = a[1]
e[2] = a[1]+a[2]
e[3] = a[3]
e[4] = a[1]+a[2]+a[3]+a[4]=e[1]+e[2]+e[3]
e[5] = a[5]
e[6] = a[5]+a[6]
e[7] = a[7]
e[8] = a[1]+a[2]+...+a[8]
解释如下：
- 每一个树状数组元素都是一个或者多个原始数组的和。
- 如何确定当前树状数组是几个原始数组元素的和？
将数组下标i表示为二进制，i从末尾开始连续0的个数定义为k。那么
e[i]=a[i-2^k +1]+a[i-2^k+2]+...+a[i]。
例如：e[8(1000)] = a[1]+a[2]+...+a[8]
后缀前缀
为了方便构造和使用树状数组，定义前缀和后缀两个操作。后缀一般在初始化和更新BIT数组中使用，前缀是为了求和的时候跳过重复的元素。
后缀
i的后缀为最为靠近i，且二进制末尾连续0的个数比i多的坐标。如e[2(10)]的后缀为e[4(100)]，e[4(100)]的后缀为e[8(1000)]。后缀主要用来构造和更新树状数组。
后缀的计算公式为:
//lowBit(i) = -i&i 或者 (i-1^i)&i
//e[i]的后缀为e[i+low(i)]
int lowBit(int i){
return -i&i;
}
可以通过一次完整的扫描即可构造出树状数组，扫描的过程中每次去更新当前值的后缀即可。
private void establishBIT() {
for (int i = 1; i < orgin.length; i++) {
if(i + lowBit(i)<orgin.length)
bit[i + lowBit(i)] += bit[i];
}
}
如果其中某一项发生改变，只需要更新一下与之相关的后缀的值。
//更新操作
//结构内部以下标1作为数组的开始位
public void update(int pos, int num){
if(pos<0||pos>orgin.length-1)
return;
int temp = orgin[pos+1];
orgin[pos+1] = num;
int delta = num-temp;
pos = pos+1;
while(pos<orgin.length){
bit[pos]+=delta;
pos = pos+lowBit(pos);
}
}
前缀
前缀的计算公式为：
//lowBit(i) = -i&i 或者 (i-1^i)&i
//e[i] 的前缀为e[i-lowBit(i)]
前缀一般在求和的过程中会用到。
public int sum(int p){
int res= 0;
while(p>0){
res+=bit[p];
p = p-lowBit(p);
}
return res;
}
后缀是为了不重复计算元素，因为在BIT数组中每一项都是原始数组的一个或者多个的和。
源码
public class BIT {
private int[] orgin;
private int[] bit;
public BIT(int[] inArray){
orgin = new int[inArray.length+1];
bit = new int[inArray.length+1];
for(int i=1;i<inArray.length+1;i++){
orgin[i] = inArray[i-1];
bit[i] = inArray[i-1];
}
establishBIT();
}
private BIT(){}
private void establishBIT() {
for (int i = 1; i < orgin.length; i++) {
if(i + lowBit(i)<orgin.length)
bit[i + lowBit(i)] += bit[i];
}
}
public String showBIT(){
StringBuilder sb = new StringBuilder();
for(int num : bit){
sb.append(num);
sb.append(" ");
}
return sb.toString();
}
private int lowBit(int i){
return -i&i;
}
public void update(int pos, int num){
if(pos<0||pos>orgin.length-1)
return;
int temp = orgin[pos+1];
orgin[pos+1] = num;
int delta = num-temp;
pos = pos+1;
while(pos<orgin.length){
bit[pos]+=delta;
pos = pos+lowBit(pos);
}
}
public int sum(int p){
int res= 0;
while(p>0){
res+=bit[p];
p = p-lowBit(p);
}
return res;
}
public static void main(String[] args) {
int[] input = new int[]{1,2,4,5,2,6,8,9};
BIT bit = new BIT(input);
System.out.println(bit.showBIT());
System.out.println(bit.sum(1));
bit.update(0,4);
System.out.println(bit.showBIT());
}
}
参考资料
https://www.cnblogs.com/grandyang/p/6657956.html
https://blog.csdn.net/u011567017/article/details/52252852
https://www.byvoid.com/zhs/blog/binary-index-tree
