发布于 ,更新于 

树状数组

树状数组代替线段树。 —— zzz《常数优化与 NOILinux》

顾名思义,树状数组是一种树形结构,但是因为他独特的结构和拆分方式(二进制你又来了是吧),可以直接用数组存储。
用途是解决大部分区间修改查询问题,复杂度一般是 \(\operatorname{O}(\log n)\) ,同时常数小(暗示 线段树 不行),同时码量小,好理解(暗示 * 2),但是复杂的区间修改查询问题不能解决,同时区间最大最小值也不能用它处理(后文会说)

Update on 2023/6/7 本质上就是能够以极小的常数且严格 \(\operatorname{O}(\log n)\) 的时间复杂度进行单点修改与前缀和的维护,不过这个前缀和可以玩得比较花。

实际上原理看看就得了,这玩意板子写完了半年过去都不带忘的...

关于常数差距到底多大?S2 的同学们可以看看 S2OJ # 786,使用普通快读仅 2.60s(现在最快的我的提交记录是卡常版的),线段树解法貌似最快的是 lyq 学长的 6.69s。

基本树状数组

原理

来自学长的一张图
注意下文基本上所有东西都可以/需要搭配这个图进行理解

以求区间和的树状数组为例,树中每一个节点存储一段区间的和,询问时进行前缀和加减即可得出任意区间的和。
分区间的方法即利用二进制,对于第 \(i\) 节点来说,\(i\) 的二进制形式中最低一位 1 的位置为 \(x\),那么 \(tree_i\) 就存储了 \([i-2^x+1,i]\) 区间的和。
注意此处 \(x\)0 开始算
\(3\) 为例,\(3\) 的二进制为 0000 0011,最低一位 1 的位置是 0,则 \(tree_3\) 存储 \([3-1+1,3]\)\([3,3]\) 的区间和。
再以 \(8\) 为例,\(8\) 的二进制为 0000 1000,最低一位 1 的位置是 3,则 \(tree_8\) 存储 \([8-8+1,8]\)\([1,8]\) 的区间和。

实现

建立

实际上不用特意处理建立,直接在输入过程中每输入一个数就修改即可。

1
2
3
4
for (int i = 1; i <= n; ++i) {
cin >> t1; // tmp
modify(i,t1);
}

lowbit

本函数实现查找一个数最后一位 \(1\) 的位置。

首先声明一个冷知识(大概冷),位运算是针对内存中存储的原数据的运算,换句话说,进行位运算的是补码而不是原码。

原码即一个数本身的二进制表示,反码即在原码的基础上符号位不变其他位取反。
补码分类来说,正数的补码是它的原码,负数的补码为其反码\(+1\)

在这里我们只考虑最后一位 1 及它后面的 0
比如 0011 0100 这个二进制数,我们先把它变成负数,即按位取反后加一(易证这就是他的相反数),变为 11001011 再变为 11001100
发现了一件神奇的事情,原来最低一位 1 竟然回来了!
显然,这位 1 前面的所有数字因为被取反所以和原数完全不同;后面的所有数字原来一定是 0 取反后变成一排 1,负数的补码是反码\(+1\),从而一直进位到原来最后一位 1 这里,而它们本身变回了 0 ;又因为这位 1 被取反后是 0 所以无论如何都不会再向前进位。
从而保证对于任意一个正数 \(x\)\(-x\)\(x\) 的存储只有 \(x\) 本身最后一位 1 是相同的。
因此 lowbit() 的实现就非常简单了,直接用 x&-x,得到的结果就是原理中所说的 \(2^x\),又快又好想,用着还方便。

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

单点修改

假设修改为给第 \(x\) 个数增加 \(v\),那我们就需要修改所有包含第 \(x\) 个元素的节点,则从第 \(x\) 个节点寻找父亲节点直到根节点为止(参考上图)。
\(x\) 节点的直接父亲是 \(x+\operatorname{lowbit}(x)\),因此直接一层循环实现 \(\operatorname{O}(\log n)\) 修改。

1
2
3
4
5
void modify(int x, int v) {
for (int i = x; i <= n; i += lowbit(i)) {
tree[i] += v;
}
}

区间查询

查询区间为 \([l,r]\) 时,将问题转化为求 \([1,r] - [1,l-1]\) 的值(前缀和知识),因此我们只需要实现查询前缀和的功能即可。
因为 \(i\) 节点存储的是一段长度为 \(\operatorname{lowbit}(i)\) 的区间的和,因此取完 \(i\) 号点的值后再取 \(i-\operatorname{lowbit}(i)\) 号节点的值,直到位置变为 \(0\)(到头)即可(看不懂就结合上面图)

1
2
3
4
5
6
7
8
9
int query(int x) {
int res = 0;
for (int i = x; i; i -= lowbit(i)) {
res += tree[i];
}
return res;
}

ans = query(r) - query(l-1);

改区间查单点

上文我们解决了求前缀和的问题,本次需要查询单点,那么很容易联想到差分。更改区间对应改差分数组上的两个点,查询单点对应查询差分数组的前缀和。

区间加区间求和

发现树状数组好快于是回来补一下(2023.6.23)

对原数组进行差分,易得:

\[ d_i = a_i - a_{i-1} \newline a_i = \sum_{j=1}^i d_i \newline \]

\([1,x]\) 的区间和,即为:

\[ \begin{aligned} ans &= \sum_{i=1}^x a_i \newline &= \sum_{i=1}^x\sum_{j=1}^{i} d_i \newline &= \sum_{i=1}^x d_i(x-i+1) \newline &= \sum_{i=1}^x(1+x)d_i-\sum_{i=1}^x i\cdot d_i \end{aligned} \]

第二行到第三行那里不知道怎么推出来的话,观察每个 \(d_i\) 出现的次数,显然 \(d_1\) 出现 \(x\) 次,\(d_2\) 出现 \(x-1\) 次(除了 \(i=1\) 的时候都出现了),于是轻松推出来。

因此我们只需要维护两个树状数组,一个维护 \(d_i\) 即差分数组,另一个维护 \(i\cdot d_i\) 即可。

注意:此处树状数组维护的仍然是前缀和,\(i\cdot d_i\) 中的 \(i\) 就是修改的位置,而不是树状数组修改时循环的 \(i\)

核心代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#define N 100005

i64 id[N], d[N];
i32 n;

inline void mod(i32 pos, i64 val) {
for (i32 i = pos; i <= n; i += lowbit(i)) {
id[i] += pos * val;
d[i] += val;
}
}

inline i64 que(i32 pos) {
i64 res = 0;
for (i32 i = pos; i; i -= lowbit(i)) {
res += d[i] * (pos + 1) - id[i];
}
return res;
}

inline void modify(i32 l, i32 r, i64 val) {
mod(l, val);
mod(r + 1, -val);
}

inline i64 query(i32 l, i32 r) {
return que(r) - que(l - 1);
}