树状数组(BIT)

简介

树状数组或二元索引树（英语：Binary Indexed Tree），又以其发明者命名为 FenwickFenwick 树。最早由 PeterM.FenwickPeterM.Fenwick 于 1994 年以《A New Data Structure for Cumulative Frequency Tables[1]》为题发表在《SOFTWARE PRACTICE AND EXPERIENCE》。其初衷是解决数据压缩里的累积频率（Cumulative Frequency）的计算问题，现多用于高效计算数列的前缀和，区间和。它可以以 (logn)O(log⁡n) 的时间得到任意前缀和（区间和）。

问题引入

数组的单点修改update和区间求和range_sum问题。

使用普通数组，update时间复杂度为$O(1)$,range_sum时间复杂度为$O(n)$.

使用前缀和数组，update时间复杂度为 O(n),range_sum时间复杂度为$O(1)$.

树状数组是上述方法的一个折中，update和range_sum时间复杂度均为$O(log_2n)$。

原理

树状数组就是这样一种结构，它巧妙地利用了二进制（实际上，树状数组的英文名 BIT，直译过来就是二进制下标树）。例如 11，转化为二进制数就是$(1011)_2$ ，如果我们要求前 11 项和，可以分别查询 $ ((0000)_2, (1000)_2] $ , $ ( (1000)_2, (1010)_2 ] $, $ ( (1010)_2, (1101)_2 ] $ 的和再相加。这三个区间怎么来的呢？其实就是不断地去掉二进制数最右边的一个 1的过程（如下图）。

二进制数最右边的一个 1，连带着它之后的 0 为lowbit(x)（稍后再来看如何实现）。那么我们用$C_i$维护区间$ (A_i - lowbit(A_i), A_i] $ 的区间和，这样显然查询前 n 项和时需要合并的区间数是少于 $ log_2n $的。树状数组的结构大概像下面这样：

可用如下公式表示：

$$ C[i] = A[i - 2^k+1] + A[i - 2^k+2] + ... + A[i] $$

其中: $k$表示 i 的二进制中从最低位到高位连续零的长度。

lowbit

一个数的二进制表示中最低的一位1。

1
2
3
int lowbit(x) {
    return x & -x;
}

优缺点

优点：修改和查询的复杂度都是$O(logN)$，相比线段树系数要少很多，比传统数组要快，而且容易写。
缺点：是遇到复杂的区间问题还是不能解决，功能还是有限。

应用场景

一般用于解决大部分基于区间上的更新以及求和问题。

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#define low(i) ((i)&(-i))

void update(int pos,int v) {
    for(int i=pos;i<=n;i+=low(i))
        c[i]+=v;//单点修改
}

int query(int pos) {
    int res=0;
    for(int i=pos;i;i-=low(i))
        res+=c[i];
    return res;//询问区间[1,pos]的权值和
}

int range_query(int a, int b) {
    return query(b) - query(a-1);
}

树状数组(BIT)

相关文章：