Loading... # 适用场景 树状数组是一种适用于多次单点修改统计区间和问题的数据结构。 # 基本思想 `Binary Indexed Tree` 求和的基本思想在于,给定需要求和的位置 `i` ,例如 `13` ,我们可以利用其二进制表示法来进行分段(或者说分层)求和:`13 = 2^3 + 2^2 + 2^0`,则`prefixSum(13) = RANGE(1, 8) + RANGE(9, 12) + RANGE(13, 13) `(注意此处的`RANGE(x, y)`表示数组中第`x`个位置到第`y`个位置的所有数字求和)。如下面例子中所示: ``` arr = [1, 7, 3, 0, 5, 8, 3, 2, 6, 2, 1, 1, 4, 5] prefixSum(13) = RANGE(1, 8) + RANGE(9, 12) + RANGE(13, 13) = 29 + 10 + 4 = 43 ``` 那么只要我们提前计算好这些`RANGE(x,y)`,便可以对相应的序列进行快速求和。 下面是构造树状数组的方法(填坑法): ![](https://www.onesnowwarrior.cn/usr/uploads/2022/05/1194133836.png) 图中最上面是原数组,中间代表了树状数组各元素的意义,即`RANGE(x,y)`,而最下面便是原数组对应的树状数组。 ## 利用树状数组求区间和 利用树状数组,我们可以发现: ``` prefixSum(13) = prefixSum(0b00001101) = BIT[13] + BIT[12] + BIT[8] = BIT[0b00001101] + BIT[0b00001100] + BIT[0b00001000] ``` 其中`BIT`即树状数组,而从二进制位我们可以发现一个很有意思的结论,即我们实际上是在将下标`13`每次减少一个最低位的`1`所在位对应的数字,直到小于`1`为止,将这些下标对应的元素累加起来便是`RANGE(1,13)`的和。 总结起来就像这样: ![](https://www.onesnowwarrior.cn/usr/uploads/2022/05/640281674.png) 这个结构可以抽象成一颗树一样: ![](https://www.onesnowwarrior.cn/usr/uploads/2022/05/2267316796.png) 寻找父节点的操作便是`lowbit` ,也即上述所发现的结论,假设当前节点下标为 `x` ,则 `lowbit(x) = x & -x`。 这样,我们就可以通过树状数组快速求区间和了。 ## 更新数组中的元素 而关于如何进行单点修改,我们以`update(5,2)`为例: ![](https://www.onesnowwarrior.cn/usr/uploads/2022/05/1323827065.png) 我们可以发现,单点修改的过程恰好与求区间和的过程相反,在此处,我们需要从`5`开始,对`5`进行`lowbit`的增加,直至超出数组范围,对所经过的下标对应的元素均进行累加,即可完成一次单点修改。 ## 树状数组的建立 第一种方法很简单,遍历数组中的每一个元素,对其使用`update(i + 1, elem)`即可,这是一种`O(nlog n)`时间复杂度的构造方法 第二种方法是一种时间复杂度`O(n)`的方法,其步骤如下(数组下标从0开始): 给定一个长度为`n`的输入数组`list`。 1. 初始化长度为`n + 1`的`Binary Indexed Tree`数组`bit`,并将`list`中的数字对应地放在`bit[1]`到`bit[n]`的各个位置。 2. 对于`1`到`n`的每一个`i`,进行如下操作: 令`j = i + (i & -i)`,若`j < n + 1`,则`bit[j] = bit[j] + bit[i]` # 代码实现 ```cpp class BinaryIndexTree { private: int *tr; inline int lowbit(int x) { return x & -x; } public: BinaryIndexTree(int arr[], int n) { tr = new int[n + 1]; for (int i = 0; i < n; ++i) tr[i + 1] = arr[i]; for (int i = 1; i < n + 1; ++i) { int j = lowbit(i); if (j < n + 1) tr[j] += tr[i]; } } void add(int x, int v) { for(int i = x; i < n + 1; i += lowbit(i)) tr[i] += v; } int query(int x) { int ans = 0; for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i]; return ans; } } ``` # 参考文章 [树状数组(Binary Indexed Tree),看这一篇就够了](https://blog.csdn.net/Yaokai_AssultMaster/article/details/79492190) Last modification:May 26, 2022 © Allow specification reprint Support Appreciate the author AliPayWeChat Like 如果觉得我的文章对你有用,请随意赞赏