树状数组（Binary Indexed Tree）

9183

2019.10.22

2019.12.23

发布于未知归属地

树状数组或二叉索引树（英语：Binary Indexed Tree），又以其发明者命名为 Fenwick 树。其初衷是解决数据压缩里的累积频率（Cumulative Frequency）的计算问题，现多用于高效计算数列的前缀和，区间和。它可以以 $O (lo g n)$ 的时间得到任意前缀和，并同时支持在 $O (lo g n)$ 时间内支持动态单点值的修改。空间复杂度 $O (n)$ 。
摘自维基百科

文章先介绍低位运算（lowbit）的基本知识，再提及如何将一个整数划分为 $l o g n$ 个区间的运算过程，进而延展到如何将线性序列以树行结构进行存取，接着介绍了高级数据结构——树状数组的两个基本操作——查询前缀和与单点增加，最后介绍了树状数组的一个应用——求解逆序对数。

lowbit（低位）运算

$l o w bi t (n)$ 定义为非负整数 $n$ 在二进制表示下 “最低位的 1 及其后边所有的 0” 构成的数值。

比如： $n = 10$ ，其二进制表示为 $(1010)_{2}$ ，则其低位 $l o w bi t (10) = (10)_{2} = 2$ 。

公式

$l o w bi t (n) = n & (\sim n + 1) = n & (- n)$

如何计算一个整数 $n$ 中二进制表示下所有位是 1 的数值？

比如 $n = 10$ ，则其二进制表示下所有位是 1 的数值有： $(10)_{2} = 2$ ， $(1000)_{2} = 8$ 。

朴素算法需要枚举整数中所有的位，时间复杂度为 $O (l e n)$ ， $l e n$ 为整数 $n$ 的二进制表示下的位数。

为了高效获取二进制表示下所有位是 1 的数值，可以利用 $l o w bi t$ 运算，得到时间复杂度 $O (l e n)$ ， $l e n$ 为二进制表示下为 1 的位的个数。

比如 $n = 10$ ， $l o w bi t (10) = 2$ ；接着另 $n = n - l o w bi t (n) = 10 - 2 = 8$ ，则 $l o w bi t (n) = l o w bi t (8) = 8$ ；接着另 $n = n - l o w bi t (n) = 8 - 8 = 0$ ，停止。

为了得到 $n$ 的第几位为 1，可以对 2 和 8 分别取对数，即 $lo g_{2} 2 = 1$ , $lo g_{2} 8 = 3$ 。由于 C++ math.h 库的 $lo g$ 函数是以 $e$ 为底的实数运算，并且复杂度常数较大，所以可以通过预处理，利用哈希表来代替 $lo g$ 运算。

代码

C++

const MAX_N = 1 << 20;
int H[MAX_N + 1];
for (int i = 0; i <= 20; ++i) H[1 << i] = i;
while (cin >> n) {
    while (n > 0) {
        cout << H[n & -n] << ' ';
        n -= n & -n;
    }
    cout << endl;
}

树状数组

假设整数 $n$ ，其二进制表示形式为：

$n = 2^{i_{1}} + 2^{i_{2}} + ... + 2^{i_{m}} ， i_{1}, i_{2} ... i_{m}$ 代表二进制表示下位为1的索引下标值，且假设 $i_{1} > i_{2} > ... > i_{m}$ 。

那么，可以将区间 $[1, n]$ 划分成 $lo g n$ 个小区间

$[1, 2^{i_{1}}]$
$[2^{i_{1}} + 1, 2^{i_{1}} + 2^{i_{2}}]$
...
$[2^{i_{1}} + 2^{i_{2}} + ... + 2^{i_{m} - 1} + 1, 2^{i_{1}} + 2^{i_{2}} + ... + 2^{i_{m}}]$

比如， $n = 7 = 2^{2} + 2^{1} + 2^{0}$ ，那么 $[1, 7]$ 区间可以划分成 $[1, 4]$ , $[5, 6]$ 和 $[7, 7]$ ，其区间长度分别为 $l o w bi t (4) = 4$ , $l o w bi t (6) = 2$ 和 $l o w bi t (7) = 1$ 。

利用 $l o w bi t$ 运算计算区间：

C++

while (x > 0) {
    printf("[%d, %d]\n" x - lowbit(x) + 1, x);
    x -= lowbit(x);
}

树状数组是基于以上思想的数据结构，基本用途是维护序列的前缀和。

那么，假设有序列 $A = {1, 2, 3, 4, 5, 6, 7, 8}$ ，现在的问题就是如何将这个序列划分成 $lo g n$ 个小区间。不妨，利用序列的索引值（以 1 为起点开始计数），根据上述计算区间的方式，将其以如下树形结构展开。

{:align=center}

树状数组（Binary Indexed Tree）以树形结构展开的序列 A

此时，以树形结构展开的序列 A 中的每一个节点都对应着树状数组中的一个值。那么这个值为以当前节点为根的子树中所有节点值的总和。

接着，我们看下以树形结构展开的树状数组是什么样的。

{:align=center}

以树形结构展开的树状数组（Binary Indexed Tree）

Index 代表序列 A 中元素的索引，为了方便，以 1 为起点计数
Original Value 代表序列 A 中的元素值
BIT Value（Binary Indexed Tree Value)代表树状数组中的值
Binary bit 代表索引值的二进制形式
Low bit 代表索引值的二进制形式下的地位

上图中最大的区别是某些节点中的值发生了变化。这是因为，在以树形结构展开的树状数组中的每一个值代表的是一个区间的总和。这个区间即为我们上述求解的区间，比如一个整数 7，可以将其划分成 $[1, 4]$ , $[5, 6]$ 和 $[7, 7]$ 三个小区间。那么，这三个小区间的右端值作为索引对应的树状数组中的值即为当前区间元素的总和。

比如 $I n d e x = 4$ 对应的树状数组的值为（BIT Value）10，它代表 $[1, 4]$ 这个区间的和。

再比如 $I n d e x = 6$ 对应的树状数组的值为 11，它代表 $[5, 6]$ 这个区间的和。

基本操作

树状数组支持两个基本操作——查询前缀和，单点增加。

查询前缀和

在寻求序列A的前n项的前缀和时，等于 $n$ 代表的 $lo g n$ 个区间的总和。

C++

int query(int x) {
    int ans = 0;
    for (; x; x -= x & -x) ans += bit[x];
    return ans;
}

单点增加

观察父子节点的关系，可以推算出，父节点的索引 parent(i)，为其子节点索引值 + 其低位—— $p a re n t (i) = i + l o w bi t (i)$ 。

C++

void update(int x, int delta) {
    for (; x; x += x & -x) bit[x] += delta;
}

关于查询前缀和与单点增加的计算过程，可以观看下面视频展示的动画。

获取视频信息中...

树状数组与逆序对

对于一个序列 $A$ ，如果 $i < j$ ，并且 $A [i] > A [j]$ ，那么则称 $A [i]$ 与 $A [j]$ 构成逆序对。利用树状数组数据结构可以求解序列 $A$ 中的逆序对个数。

逆序遍历序列
利用树状数组的性质，使用 $q u ery$ 操作获取每一个元素的逆序对数
将当前元素更新（ $u p d a t e$ ）到树状数组中
循环迭代上述步骤，直到遍历所有元素

C++

int cnt = 0;
for (int i = A.size() - 1; i >= 0; --i) {
    cnt += query(A[i]);
    update(A[i], 1);
}

在每一次更新（ $u p d a t e$ ）树状数组时，以元素的值作为树状数组的索引，更新的值为 +1，代表个数。

在每一次获取（ $q u ery$ ）逆序对数时，存在于树状数组中的元素的索引值都比当前元素的大（逆序遍历），那么自然获取到的树状数组的值即为索引值比当前元素的大，且值比当前元素的小的个数。

注意，上述的求解过程时，如果序列A的值范围较大时，那么需要离散化处理。

参考

原文

树状数组（Binary Indexed Tree）