「观前提醒」
「文章仅供学习和参考，如有问题请在评论区提出」
- 前言
- 定义
- 基本概念
- 基本原理
-
单点修改
- 分析
- 代码实现
-
区间查询
- 分析
- 代码实现
- 整体代码
- 练手题目
- 小结
- 参考资料
前言
这也算是我写正儿八经的博客，因为没怎么写过，所以可能有些地方没讲好或者有点啰嗦。但是我也会尽可能地解释明白其中的具体实现方法。要是有什么错误和问题，欢迎在评论区里指正和提问。
定义
树状数组是一种支持 单点修改 和 区间查询 的数据结构。
普通的树状数组只能用来维护像加法、乘法、异或等，这样满足结合律和可差分的信息。
- 结合律：((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]) 并不是直接存储的前缀和，而是存储了一段相对应的区间值。具体如下，
首先我们定义: sum[x, y] = &sum_{i = x}^{y} a[i] \
C[1] = sum[1, 1] &= a[1] \
C[2] = sum[1, 2] &= a[2] + C[1] \
C[3] = sum[3, 3] &= a[3] \
C[4] = sum[1, 4] &= a[4] + C[3] + C[2] \
C[5] = sum[5, 5] &= a[5] \
C[6] = sum[5, 6] &= a[6] + C[5] \
C[7] = sum[7, 7] &= a[7] \
C[8] = sum[1, 8] &= a[8] + C[7] + C[6] + C[4] \
&… \
C[16] = sum[1, 16] &= a[16] + C[15] + C[14] + C[12] + C[8]\
&…
end{align}
]
这样的话，我们在查询前缀和的时候就只需要把相对应的区间加和就行了。
例如，当我们要获取 (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]) 。然后观察它们的二进制表示，
8(1000_{2}) enspace = enspace
& 4(0100_{2}) enspace + enspace 0100_{2} \
& 6(0110_{2}) enspace + enspace 0010_{2} \
& 7(0111_{2}) enspace + enspace 0001_{2} \
end{align}
]
同样我们也能得出结论，(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{align}
x &= enspace …1001100_{2} \
-x &= enspace …0110100_{2} \
x enspace & -x &= enspace …0000100_{2} \
end{align}
]代码实现
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 区间查询
分析
所谓区间查询，也就是利用前缀和 (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) 所对应的数值。模拟过程就是，
sum[1, 13] = &C[12] + C[8] + C[0]enspace (默认 C[0] 为 0)\
13 &= 1011_{2} \
回退 enspace 0001_{2} enspace 12 &= 1010_{2} \
回退 enspace 0010_{2} enspace enspace 8 &= 1000_{2} \
回退 enspace 1000_{2} enspace enspace 0 &= 0000_{2} \
end{align}
]
然后我们就能发现，这其实就是获取 (x) 每一位 (1) （从低位到高位）所对应的数值。
x = & 2^{b_{1}} + 2^{b_{2}} + … + 2^{b_{k}} \
sum[1, x] = enspace
& C[x – 2^{b_{1}}] \
+ &C[x – 2^{b_{1}} – 2^{b_{2}}] \
+ & … \
+ &C[x – 2^{b_{1}} – 2^{b_{2}} – … -2^{b_{k}}] \
end{align}
]
那么这样的话就也需要用到 (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
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;
// 获取原数组数据
for (int i = 1; i > a[i];
// 建立树状数组
for (int i = 1; i 练手题目
P3374 【模板】树状数组 1 – 洛谷
P3368 【模板】树状数组 2 – 洛谷
小结
树状数组巧妙地运用了二进制的存储逻辑，使得能够在 (O(logN)) 内完成单点修改和区间查询 。虽然它的应用场景有局限性，有些问题还是需要用到线段树来解决。但是树状数组胜在代码简单，用的时候很好敲（相对于敲一个线段树）。
而且这里只是讲了树状数组最基本的应用，上面的例题也都是模板题。至于树状数组的拓展使用，之后应该会再写的。。。。
参考资料
树状数组 – OI Wiki (oi-wiki.org)：https://oi-wiki.org/ds/fenwick/
机房租用，北京机房托管，大带宽租用，IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net
