Fenwick Tree(Binary Index Tree) - 树状数组

描述

对于包含 n 个数字的数组 s ，修改其中若干成员 s[i] （其中 1 \le i \le n ）后，求数组 s 在区间 [p,q] （其中 1 \le p \le q \le n ）上的所有成员之和。一般是在修改了成员之后，求和时遍历区间 [p,q] 相加求该区间的和。修改成员 s[i] （其中 1 \le i \le n ）的时间复杂度为 O(1) ，求 s[p,q] 区间的和的时间复杂度为 O(n) 。

而树状数组可以更快的进行区间求和，将该问题转化为前缀和，即 s[p,q] = s[1,q] - s[1,q] 。类似所有整数都可以表示成 2 的幂和，也可以把一串序列表示成一系列子序列的和。其中，子序列的个数是其二进制表示中 1 的个数，并且子序列代表的 s[i] 的个数也是 2 的幂。

(1) LowBit函数

函数LowBit用于计算一个数字的二进制形式下最低位的 1 代表的十进制的值。比如 34{10} = 10,0010_2 最低位的 1 代表的十进制值为 2{10} ， 12{10} = 1100{2} 最低位的 1 代表的十进制值为 4{10} ， 8{10} = 10002 最低位的 1 代表的十进制值为 8{10} ，则有 LowBit(34) = 2 ， LowBit(12) = 4 ， LowBit(8) = 8 。

在C/C++中由于补码的原因，LowBit函数实现如下：

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

或者利用计算机补码的特性，写成：

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

内存中的数字按照补码存储（正整数的补码与原码相同，负整数的补码是原码取反加一，并且最高位 bit 设置为 1 ）。比如：

34{10} = 0010,0010{2} ，则 - 34{10} = 1101,1110{2} ；

12{10} = 0000,1100{2} ，则 - 12{10} = 1111,0100{2} ；

8{10} = 0000,1000{2} ，则 - 8{10} = 1111,1000{2} ；

对于非负整数 x ， x 与 - x 进行位与操作，即可得到 x 中最低位的 1 所代表的十进制的值。比如：

34{10} \; \& \; (- 34{10} ) = 0010,0010{2} \; \& \; 1101,1110{2} = 10{2} = 2{10}

12{10} \; \& \; (- 12{10} ) = 0000,1100{2} \; \& \; 1111,0100{2} = 100{2} = 4{10}

8{10} \; \& \; (- 8{10} ) = 0000,1000{2} \; \& \; 1111,1000{2} = 10002 = 8{10}

额外需要注意的是，CPU架构中大端模式（Big-Endian）和小端模式（Little-Endian）的区别并不会影响该计算。因为大端和小端影响的是数据在内存中存放的顺序，当数据被CPU加载到寄存器中时，所有的位操作都是在寄存器上进行的，不会影响位操作，因此位操作可以从纯数学计算的角度来看。

(2) 维护 s 前缀和的数组 bit

对于长度为 n 的数组 s （该算法需要数组下标从 1 开始，因此数组 s 的范围为 [1,n] ），数组 bit 中的元素 bit[i] = \sum_{j = i-LowBit(i)+1}^{i}s[j] 。比如：


\begin{array}{lcr}
bit[1] = \sum{j = 1-1+1}^{1}s[j] = s[1] \
bit[2] = \sum{j = 2-2+1}^{2}s[j] = s[1]+s[2] \
bit[3] = \sum{j = 3-1+1}^{3}s[j] = s[3] \
bit[4] = \sum{j = 4-4+1}^{4}s[j] = s[1]+s[2]+s[3]+s[4] \
bit[5] = \sum{j = 5-1+1}^{5}s[j] = s[5] \
bit[6] = \sum{j = 6-2+1}^{6}s[j] = s[5]+s[6] \
bit[7] = \sum{j = 7-1+1}^{7}s[j] = s[7] \
bit[8] = \sum{j = 8-8+1}^{8}s[j] = s[1]+s[2]+s[3]+s[4]+s[5]+s[6]+s[7]+s[8] \
bit[9] = \sum_{j = 9-9+1}^{9}s[j] = s[9]
\end{array}

在数组 bit 的基础上，求数组 s 中 [0,p] 的和，只需累加所有 bit[i] ，其中初始时 i = p ，每累加一次(bit[i])，(i)值减去(LowBit(i))，直到(i \le 0)。（这里我暂时也没找到更好的讲解方法，解释的不是很清晰）

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

树状数组（Fenwick tree）：

源码

import, lang:”c_cpp”

测试

import, lang:”c_cpp”