Fenwick Tree(Binary Indexed Tree) - 树状数组（二进制索引树）

树状数组（二进制索引树）

给定 $n$ 个数字 $s = [x_{1}, x_{2}, x_{3}, \dots, x_{n}]$ ，求区间 $s[p,q)$ （其中 $1 \leq p \lt q \leq n$ ）上的所有成员之和（简称区域和/区间和）

$\sum_{i=p}^{q-1} x_i$

其中 $0 \leq p \lt q \lt n$ 。该区间可以修改任意元素的值。

区间上任意位置 $s[i]$ 的值可以修改，但所有元素都恒为非负整数。

循环累加数组的算法和Segment Tree算法都可以解决该问题，Fenwick树（树状数组/二进制索引树）与Segment Tree同样在时间复杂度 $O(log_2 n)$ 内求出某个区域上的和，但空间复杂度更低。实际上由于字节操作，FenwickTree不但占用内存少，且速度更快（内存更紧凑的软件速度更快）。

设 $sum(n) = \sum_{i=1}^{n} s[i]$ ，那么 $s[p,q)$ 的区间和可以表示为 $sum(q-1) - sum(p-1)$ 。本问题可以转化为求区间 $s$ 上前 $n$ 个元素之和的问题。

任意非负整数都可以表示为 $2$ 的次方和，比如 $3 = 2^1 + 2^0, 7 = 2^2 + 2^1 + 2^0, 8 = 2^3$ 。所以任意非负整数可以用一个代表bit的数组表示： $3 = [0, 0, 1, 1]$ ， $7 = [0, 1, 1, 1]$ ， $8 = [1, 0, 0, 0]$ ，即二进制数字 $0011, 0111, 1000$ 。那么区域 $s$ 可以用 $n$ 个二进制数组来表示所有数字，用Fenwick树结构来表示：

引入最低有效位lowbit函数来构造Fenwick树上的每个节点。 $lowbit$ 是一个非负整数的二进制数字中，最低的非 $0$ 位的数字（比如 $lowbit_{3} = 1, lowbit_{6} = 2, lowbit_{8} = 8, lowbit_{11} = 1$ ，显然奇数有 $lowbit_{ord} \equiv 1$ ）：

令Fenwick树上的节点 $x$ 存储值

$t[x] = \sum_{i=x-lowbit(x)+1}^{x} s[i]$

比如

$\begin{matrix} t[1] & = \sum_{i=1-1+1}^{1} s[i] & = \sum_{i=1}^{1} s[i] & = s[1] & x=1 \\ t[2] & = \sum_{i=2-2+1}^{2} s[i] & = \sum_{i=1}^{2} s[i] & = s[1] + s[2] & x=2 \\ t[3] & = \sum_{i=3-1+1}^{3} s[i] & = \sum_{i=3}^{3} s[i] & = s[3] & x=3 \\ t[4] & = \sum_{i=4-4+1}^{4} s[i] & = \sum_{i=1}^{4} s[i] & = s[1] + \cdots + s[4] & x=4 \\ t[5] & = \sum_{i=5-1+1}^{5} s[i] & = \sum_{i=5}^{5} s[i] & = s[5] & x=5 \\ t[6] & = \sum_{i=6-2+1}^{6} s[i] & = \sum_{i=5}^{6} s[i] & = s[5] + s[6] & x=6 \\ t[7] & = \sum_{i=7-1+1}^{7} s[i] & = \sum_{i=7}^{7} s[i] & = s[7] & x=7 \\ t[8] & = \sum_{i=8-8+1}^{8} s[i] & = \sum_{i=1}^{8} s[i] & = s[1] + \cdots + s[8] & x=8 \\ t[9] & = \sum_{i=9-1+1}^{9} s[i] & = \sum_{i=1}^{9} s[i] & = s[9] & x=9 \\ t[10] & = \sum_{i=10-2+1}^{10} s[i] & = \sum_{i=9}^{10} s[i] & = s[9] + s[10] & x=10 \\ t[11] & = \sum_{i=11-1+1}^{11} s[i] & = \sum_{i=11}^{11} s[i] & = s[11] & x=11 \\ t[12] & = \sum_{i=12-4+1}^{12} s[i] & = \sum_{i=9}^{12} s[i] & = s[9] + \cdots + s[12] & x=12 \\ t[13] & = \sum_{i=13-1+1}^{13} s[i] & = \sum_{i=13}^{13} s[i] & = s[13] & x=13 \\ t[14] & = \sum_{i=14-2+1}^{14} s[i] & = \sum_{i=13}^{14} s[i] & = s[13] + s[14] & x=14 \\ t[15] & = \sum_{i=15-1+1}^{15} s[i] & = \sum_{i=15}^{15} s[i] & = s[15] & x=15 \\ t[16] & = \sum_{i=16-16+1}^{16} s[i] & = \sum_{i=1}^{16} s[i] & = s[1] + \cdots + s[16] & x=16 \\ \cdots \end{matrix}$

那么Fenwick树上每个节点 $i$ 覆盖到的区域和如图所示：

设数字 $x$ 用 $2$ 的次方和表示为：

$x = [bit_{1}, bit_{2}, \dots, bit_{m}]$

比如 $6 = [4, 2], 8 = [8], 10 = [8, 2]$ 。那么恰好有

$sum(x) = t[x] + sum(x - lowbit(x))$

求非负整数 $x$ 的最低有效位分为以下几步：

$(1)$ 减 $1$ 使 $x$ 的最低有效位变为0（ $x - 1$ ），最低有效位之前的那些 $0$ 变为 $1$ ，比如 $1000 - 1 = 111$ ；

$(2)$ 然后异或操作（ $x \oplus (x-1)$ ）就可以将 $x$ 的最低有效位及之前的所有位设置为 $1$ ，比如 $1000 \oplus 0111 = 1111$ ；

$(3)$ 最后与原 $x$ 做与操作（ $x \wedge (x \oplus (x-1))$ ），结果即为最低有效位对应的数字；

lowbit函数的C++实现如下

int LowBit(int x) {
    return x & (x ^ (x-1));
}

或者利用反码特性实现

int LowBit(int x) {
    return x & (-x);
}

对于长度为 $n$ 的区域 $s$ ，构造Fenwick树的时间复杂度为 $O(n \cdot log_2⁡n)$ ，查询区域和的时间复杂度为 $O(log_2 n)$ ，修改区域上一个值的时间复杂度为 $O(log_2⁡n)$ ，空间复杂度为 $O(n)$ 。

二进制索引树

源码

FenwickTree.h

FenwickTree.cpp

测试

FenwickTreeTest.cpp