数据结构_树状数组 详解

数据结构_树状数组 详解 😀 Powerd By HeartFireY | -Binary Indexed Tree- |

一、简介/前导 1.前导

我们来关注这样一个问题：要求对一个数组实现单点修改、区间求和。

我们不难得知：在朴素算法下，单点修改的时间复杂度 O ( 1 ) O(1) O(1)，区间求和的时间复杂度 O ( n ) O(n) O(n)。

如果使用前缀和进行优化，区间求和的时间复杂度降为 O ( 1 ) O(1) O(1)，而单点修改的时间复杂度却变为 O ( n ) O(n) O(n)。

显然，在强数据下，这两种算法是容易超出所给时间范围的。

如果我们使用一个数组来维护每一段区间的和，对所有需要用到的区间进行求和，但如果要查询或修改的区间跨度大，则会引起大量的区间更新、合并操作。显然这也是不明智的选择。

因此，我们想要寻找一种折中的方案，使得区间求和和单点修改的时间复杂度都不会太大。那么我们需要考虑引起时间开销的原因：

对于单点修改，在前缀和下需要对区间进行更新操作；对于区间求和，在朴素算法下需要对区间内的子区间进行合并操作。

那么我们能否找到这样一种结构：单点修改时引发的区间更新数量不会太多、区间查询时需要进行合并的对象不会太多，那么这就需要引出我们本篇文章的主要对象：树状数组(BIT)。

2.简介

树状数组(Binary Indexed Tree)又称二叉搜索树，简称BIT。

树状数组是这样一种数据结构：在 O ( log ⁡ n ) O(\log n) O(logn)时间复杂度下，支持单点修改、区间查询的一种储存结构。

对于树状数组，我们很容易联系到线段树：线段树支持单点修改、区间修改、区间查询。同时在 L a z y Lazy Lazy标记的辅助下，能够实现很优秀的区间修改算法。如下是一棵线段树的结构：

但是在许多场景下，我们并不要进行区间修改，仅仅是进行简单的单点修改和区间查询，因此我们可以引入树状数组。与线段树相比，树状数组的代码更为简洁，在解决一类问题(单点修改)时具有突出的优势。如下是一个树状数组的结构示意图：

我们通过这张图对树状数组的结构进行分析，并介绍具体的原理。 这里可能会引发一个疑问：上图实际上并不是一棵二叉树？ 我们通过一个动画来解释这个问题：

二、树状数组 详解 1.区间查询 详解

首先，我们给出一个长度为 8 8 8的数组(为了计算方便，我们约定下标从 1 1 1开始)。其树状数组结构如下图所示：

现在我们复现一下一开始提出的问题，单点修改，区间求和。

如果我们要求前 8 8 8项的和，那么我们需要查询的区间是 ( ( 0000 ) 2 , ( 1000 ) 2 ] ((0000)_2,(1000)_2] ((0000)2​,(1000)2​]；

如果我们要求前7项的和，那么我们需要查询的区间是 ( ( 0000 ) 2 , ( 0100 ) 2 ] , ( ( 0100 ) 2 , ( 0110 ) 2 ] , ( ( 0110 ) 2 , ( 0111 ) 2 ] ((0000)_2,(0100)_2],((0100)_2, (0110)_2],((0110)_2, (0111)_2] ((0000)2​,(0100)2​],((0100)2​,(0110)2​],((0110)2​,(0111)2​];

. . . ... ...

查询的区间是如何得到的？区间右端点不断地取最低为 1 1 1的位并改为 0 0 0，作为左端点，直到没有 1 1 1(即为 0 0 0)时结束。

我们再学习状态压缩的时候曾经使用过这样一个函数 l o w b i t ( x ) lowbit(x) lowbit(x)，它的作用是返回 x x x二进制表示中最低位为 0 0 0的数。

#define lowbit(x) ((x) & (-x))

这么做的依据是什么？我们回到结构图中，很显然可以看出： c 2 c_2 c2​ 管理的对象是 a 1 a_1 a1​& a 2 a_2 a2​； c 4 c_4 c4​ 管理的对象是 a 1 a_1 a1​& a 2 a_2 a2​& a 3 a_3 a3​& a 4 a_4 a4​； c 6 c_6 c6​ 管理的对象是 a 5 a_5 a5​& a 6 a_6 a6​； c 8 c_8 c8​ 则管理全部 8 8 8 个数。

如果我们要求前 7 7 7项的和，我们从 c 7 c_7 c7​开始， c 7 c_7 c7​只管理一个点 a 7 a_7 a7​；继续向前找会找到 c 6 c_6 c6​，而 c 6 c_6 c6​管理 a 5 a_5 a5​& a 6 a_6 a6​；那么我们跳过被管理的元素继续向前找会找到 c 4 c_4 c4​，管理的是 a 1 a_1 a1​& a 2 a_2 a2​& a 3 a_3 a3​& a 4 a_4 a4​。那么显然，查询操作结束。不难发现：查询的过程被不停的压缩优化。

那么我们只需要通过 c i c_i ci​维护区间 ( a i − l o w b i t ( a i ) , a i ] (a_i - lowbit(a_i), a_i] (ai​−lowbit(ai​),ai​]，这样在查询前合并的区间数是小于 log ⁡ 2 n \log_2 n log2​n的。我们将 a a a数组和 c c c数组的对应关系用结构图进行说明：

2.单点修改 详解

解决了区间查询的问题，我们来解决单点修改的问题。如何维护树状数组 c c c呢？

假如我们要对 A [ 5 ] A[5] A[5]进行修改，那么我们从 c 5 c_5 c5​出发，沿着 c 5 → c 6 → c 8 c_5 \rightarrow c_6 \rightarrow c_8 c5​→c6​→c8​的路径进行修改。这条路径是怎样得到的？

我们将下标二进制化，再来观察路径： c [ 0101 ] → c [ 0110 ] → c [ 1000 ] c[0101] \rightarrow c[0110] \rightarrow c[1000] c[0101]→c[0110]→c[1000]，不难发现：更新路径上相邻结点 c i c_i ci​ 和 c i + 1 c_{i + 1} ci+1​ 刚好相差一个 l o w b i t ( i ) lowbit(i) lowbit(i)，那么更新的过程就很简单了，循环取 l o w b i t ( i ) lowbit(i) lowbit(i)更新 c i 、 c i + l o w b i t ( i ) . . . c_i、c_{i + lowbit(i)}... ci​、ci+lowbit(i)​...直到 i = M A X N i = MAXN i=MAXN ( M A X N MAXN MAXN为数组长度)。

这样，我们就得到了一种可以在 O ( log ⁡ n ) O(\log n) O(logn)时间下支持单点修改和区间查询的数据结构。

3.两种操作的具体实现

经过上述分析，我们可以对两种操作进行实现：

#define lobit(x) ((x) & (-x))
#define MAXN $Array_Max_Sizes$
int a[MAXN], len;
int tree[MAXN];
//树状数组初始化(O(n)建树)
inline void init(){
    memset(tree, 0, sizeof(tree));
    for(int i = 1, tmp = 0; i