树状数组

「观前提醒」

「文章仅供学习和参考，如有问题请在评论区提出」

前言#

这也算是我写正儿八经的博客，因为没怎么写过，所以可能有些地方没讲好或者有点啰嗦。但是我也会尽可能地解释明白其中的具体实现方法。要是有什么错误和问题，欢迎在评论区里指正和提问。

定义#

树状数组是一种支持 单点修改 和 区间查询 的数据结构。

普通的树状数组只能用来维护像加法、乘法、异或等，这样满足结合律和可差分的信息。

• 结合律：$(x\circ y)\circ z=x\circ (y\circ z)$ ，其中 $\circ$ 是一个二元运算符。
• 可差分：具有逆运算的运算，即已知 $x\circ y$ 和 $x$ 可以求出 $y$ 。

基本概念#

对于普通的数组来存储数据，修改一个数的时间复杂度是 $O(1)$ 的，但是区间查询则是 $O(N)$ 。而对于前缀和数组来说，虽然它能够在 $O(1)$ 的时间复杂度内进行区间查询，但是一旦数据有了修改，仍然要再 $O(N)$ 地重新构造。

所以对于这种单点修改和区间查询都有的操作，这两种数据结构都不能很好地完成任务。而树状数组就用了一种折中的法子来应对两种操作都有的情况，利用二进制的原理来维护前缀和，从而达到：

• 时间复杂度
  • 单点修改：$O(logN)$
  • 区间查询：$O(logN)$
• 空间复杂度：$O(N)$

基本原理#

树状数组是根据二进制的原理对数据进行存储，基本存储逻辑如下图所示。

$a[i]$ 代表原数组的存储数据，$C[i]$ 代表树状数组的存储数据。而我们从图中发现，$C[i]$ 并不是直接存储的前缀和，而是存储了一段相对应的区间值。具体如下，

这样的话，我们在查询前缀和的时候就只需要把相对应的区间加和就行了。

例如，当我们要获取 $i=15$ 时的前缀和 $sum[1,15]$ 时，就只需要把 $1\sim 15$ 里的 $C[j]$ 和就行，即 $sum[1,15]=C[15]+C[14]+C[12]+C[8]$ 。

那么对于 $C[i]$ 要存储的区间值的逻辑是什么呢？就是为什么 $C[10]=sum[9,10]$ ，而不是 $sum[1,10]$ 或者存储其他的区间值。而这里就是树状数组对二进制原理的应用，$C[i]$ 要存储的区间值就和 $x$ 的二进制表示有关。

根据二进制原理，对于一个正整数 $x$ ，可以表示为

$b_i$ 代表 $x$ 的二进制表示中，从低位到高位，第 $i$ 个 $1$ 出现的位次（从 $0$ 开始）。

例如： $x=11({1011}_2)$，那么 $11=2^0+2^2+2^3=1+2+8$ 。

那么我们发现， $C[x]$ 要存储的区间值其实就是 $sum[x-2^{b_1}+1,x]$ 。这里的 $2^{b_1}$ 代表 $x$ 的二进制表示中最低位 $1$ 所对应的值，即

例如，$x=12({1100}_2)$，最低位 $1$ 所对应的值为 $2^2$，所以 $C[12]=sum[12-2^2+1,12]=sum[9,12]$ 。

单点修改#

分析#

从上面我们知道树状数组 $C[x]=sum[x-2^{b_1}+1,x]$ ，那我们每次对于 $a[i]$ 的修改操作都得保证这种逻辑是存在的。

假设现在要给$a[3]$ 加上 $V_0$ 。然后我们观察图发现， $C[3],C[4],C[8],C[16]...$ ，它们的值是从 $a[3]$ 那里作为一部分加和得来的。那么为了保证数据存储逻辑的成立，就得把它们的值也都加上$V_0$ 。

因为 $C[x]$ 维护的是一个区间和，如果区间里的某一个值发生改变，那么 $C[x]$ 也要做出相应的修改。同理，如果 $C[x]$ 所维护区间被 $C[y]$ 所包含，那么 $C[y]$ 也需要做出相应的修改，然后一直往后找谁也需要被修改。那么我们就会发现，这不就是一个不断寻找自己父节点的过程（毕竟树状数组也算是个树结构），直到数组结尾。

那么问题来了，该怎么寻找 $C[x]$ 的父节点呢？

这里先给出结论，对于 $C[x]$ ，它的父节点就是 $C[x+2^{b_1}]$ 。这里的 $2^{b_1}$ 和上面同理，代表 $x$ 最低位的 $1$ 所对应的值。那这个要怎么理解呢？

一种思路是，我们可以观察存储的逻辑图来找规律。我们发现 $C[x]$ 的区间长度就等于 $C[x]$ 到其父节点的距离，而 $C[x]$ 的区间长度就为 $2^{b_1}$ 。

另一种思路就是，我们可以通过二进制来看。通过上图我们知道，$C[8]$ 的子节点有 $C[4],C[6],C[7]$ 。然后观察它们的二级制表示，

同样我们也能得出结论，$x$ 的父节点为 $x+2^{b_1}$ 。至于 $x$ 最低位 $1$ 所代表的数值，可以通过 $lowbit(x)$ 来求。

这样每次通过 x += lowbit(x); 来更新数值，直到数组结尾 $n$，最多需要执行 $logn$ 次，所以一次修改操作的时间复杂度就是 $O(logN)$ 。

lowbit(x) 解释（会的话可以直接跳过）

---

功能：可以用来求一个非负整数数 $x$ 最低位 $1$ 所代表的数值。

原理：它是利用了负数的补码特性。

我们知道，一个负数 $-x$ 的二进制表示，是在其对应正数 $x$ 的二进制表示进行取反加一 得来的。

例如，43 的二进制表示为 
           ...101011	// 前面省略 0
按位取反    ...010100	 // 前面省略 1
	+ 1    ...010101	// 前面省略 1
最后的出来的(...010101) 就是 -43 的二进制表示

$lowbit(x)$ 是将 $x$ 和 $-x$ 进行按位与（&）操作，然后得到 $x$ 最低位 $1$ 所代表的数。

$$\begin{array}{}\text{(16)}& x& =..{.1001100}_2\text{(17)}& -x& =..{.0110100}_2\text{(18)}& x\mathrm{\&}-x& =..{.0000100}_2\end{array}$$

代码实现

void lowbit(x) {
    return x & -x;
}

如果实在不明白，可以先去学一学二进制及位运算相关的知识。

代码实现#

const int N = 1e5 + 10;

int tr[N];	// tr[] 存储树状数组数据
int a[N];	// a[] 存储原数组数据
int n;	// 数组的长度

// 返回非负整数 x 在二进制表示下最低位 1 及其后面 0 构成的数值
int lowbit(int x) { return x & -x; }

// 将序列中第 x 个数加上 c
void add(int x, int c) {
    // 不断寻找自己的父亲节点，然后加上增减的值
    for (int i = x; i <= n; i += lowbit(i))
        tr[i] += c;
}

// 使用举例
add(2, 3);	// 将序列中下标为 2 的数加上 3
add(5, -7);	// 将序列中下标为 5 的数减去 7

// 这里的每次操作都是对 tr[]进行修改, 而不会对 a[] 产生影响。

区间查询#

分析#

所谓区间查询，也就是利用前缀和 $sum[l,r]=sum[1,r]-sum[1,l-1]$ ，所以本质还是获取前缀和。

前面我们知道了树状数组每个 $C[i]$ 所存储的是区间值，而想要每次查询操作来获取前缀和，就需要把这些区间值加在一起。那么对于每次操作要选择哪些区间相加呢？

然后拿出我们的万用图进行找规律（一招鲜，吃遍天）

我们能够发现，对于 $sum[1,x]$ 值的获取，可以看成一个不断进行回退来获取 $C[i]$ 的过程。例如，$sum[1,15]=C[15]+C[14]+C[12]+C[8]$ 。而每次需要回退的长度就是每个 $C[i]$ 的区间长度，即每次获取最低位 $1$ 所对应的数值。模拟过程就是，

然后我们就能发现，这其实就是获取 $x$ 每一位 $1$ （从低位到高位）所对应的数值。

那么这样的话就也需要用到 $lowbit(x)$ 来每次获取 $x$ 最低位 $1$ 所对应的数值，从而找到需要加和的 $C[i]$ ，来实现查询前缀和的操作。

这样每次通过 x -= lowbit(x); 来更新数值，因为是对 $x$ 的二进制进行操作，所以最多需要执行 $logx$ 次，那么一次查询操作的时间复杂度就是 $O(logN)$ 。

代码实现#

const int N = 1e5 + 10;

int tr[N];	// tr[] 存储树状数组数据
int a[N];	// a[] 存储原数组数据

// 返回非负整数 x 在二进制表示下最低位 1 及其后面 0 构成的数值
int lowbit(int x) { return x & -x; }

// 查询序列前 x 个数的和
int query(int x) {
    int res = 0;
    // 不断进行回退, 直到 tr[0]
    for (int i = x; i; i -= lowbit(i))
        res += tr[i];
    return res;
}

// 操作举例
int sum1 = query(x);	// 查询 a[1] ~ a[x]的和
int sum2 = query(r) - query(l - 1);	// 查询 a[l] ~ a[r] 的和

整体代码#

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int tr[N];	// tr[] 存储树状数组数据
int a[N];	// a[] 存储原数组数据

// 返回非负整数 x 在二进制表示下最低位 1 及其后面 0 构成的数值
int lowbit(int x) { return x & -x; }

// 将序列中第 x 个数加上 c
void add(int x, int c) {
    for (int i = x; i <= n; i += lowbit(i)) 
        tr[i] += c;
}

// 查询序列前 x 个数的和
void query(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i))
        res += tr[i];
    return res;
}


int main() {
    int n;
    cin >> n;
    
    // 获取原数组数据
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    // 建立树状数组
    for (int i = 1; i <= n; i++) 
        add(i, a[i]);	// 在下标为 i 的位置加上 a[i]
    
    add(3, 20);	// 在下标为 3 的位置加上 20
    add(4, -30);// 在下标为 4 的位置减去 30
    add(15 - query(2));	// 将下标为 2 的位置的值改为 15
    
    int sum1 = query(11);	// 获取序列前 11 个数的和
    int sum2 = query(14, 3);	// 获取序列下标 3~14 的和
    
    return 0;
}

练手题目#

P3374 【模板】树状数组 1 – 洛谷

P3368 【模板】树状数组 2 – 洛谷

小结#

树状数组巧妙地运用了二进制的存储逻辑，使得能够在 $O(logN)$ 内完成单点修改和区间查询 。虽然它的应用场景有局限性，有些问题还是需要用到线段树来解决。但是树状数组胜在代码简单，用的时候很好敲（相对于敲一个线段树）。
而且这里只是讲了树状数组最基本的应用，上面的例题也都是模板题。至于树状数组的拓展使用，之后应该会再写的。。。。

参考资料#

树状数组 – OI Wiki (oi-wiki.org)：https://oi-wiki.org/ds/fenwick/