高效又好写的数据结构
简介
树状数组或二叉索引树(英语:Binary Indexed Tree),又以其发明者命名为Fenwick树,最早由Peter M. Fenwick于1994年以A New Data Structure for Cumulative Frequency Tables为题发表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解决数据压缩里的累积频率(Cumulative Frequency)的计算问题,现多用于高效计算数列的前缀和, 区间和。它可以以${\displaystyle O(\log n)}$的时间得到任意前缀和${\displaystyle \sum _{i=1}^{j}A[i],1<=j<=N}$!,并同时支持在${\displaystyle O(\log n)}$时间内支持动态单点值的修改。空间复杂度${\displaystyle O(n)}$。
——Wikipedia
简单的说,树状数组就是一个便于在 $O(\log n)$ 时间内维护一个数列 / 矩阵的前缀和,可以支持单点修改、查询,区间修改、查询的数据结构。
依据支持操作的不同(包含关系),我这里把它分为六类:
- 支持序列单点加减、区间和查询的树状数组
- 支持序列区间加减、单点查询的树状数组
- 支持序列区间加减、区间和查询的树状数组
- 支持矩阵单点加减、子矩阵和查询的树状数组
- 支持矩阵的子矩阵加减、单点查询的树状数组
- 支持矩阵的子矩阵加减、子矩阵和查询的树状数组
这些会一个一个的讲。
序列操作
单点加减、区间和查询
这个是最基础的树状数组,应该没有人不会吧……
原理就是通过维护前缀和,修改的时候像暴力维护前缀和一样一个一个往后加,不过每次增长的值不是1而是lowbit,其中“一个数取lowbit能跳到哪”这个关系连边后就形成了一个二叉搜索树。
按照Peter M. Fenwick的说法,正如所有的整数都可以表示成2的幂和,我们也可以把一串序列表示成一系列子序列的和。采用这个想法,我们可将一个前缀和划分成多个子序列的和,而划分的方法与数的2的幂和具有极其相似的方式。一方面,子序列的个数是其二进制表示中1的个数,另一方面,子序列代表的f[i]的个数也是2的幂。
——Wikipedia
比如说这一棵就是八个元素的树状数组,对照下面的表可以发现上面的连边规律(点下面的是编号,请自动忽略根节点 9 以及那条边)。
1 | 1's lowbit = 1, 1 + lowbit = 2 |
那么代码就很容易写出来了:
1 | int n, tree[MAX_SIZE]; |
区间加减、单点查询
不知道你们有没有听说过一个东西叫做「差分」
定义差分数组 d[i] = a[i] - a[i - 1]
,其中 a[]
表示原数列
那么对 d[i]
求一个前缀和就可以得出 a[i]
的值了
举个例子:1
2
3数组下标从 0 开始,元素存储从 1 开始,a[0] = d[0] = 0
a[] = {0, 1, 3, 4, 2}
d[] = {/, 1, 2, 2, -2}
发现了什么?
如何修改$\text{[L,R]}+x$?
先给结论:在$\text{L}$处$+x$,在$\text{R+1}$处$-x$
直观理解:1
2
3
4
5
6
7下标从 1 开始。
原数列:0 0 0 0 0 0
按照上面的方法 [2,4]+x
0 x 0 0 -x 0
看看前缀和之后会发生什么……
0 x x x 0 0
!!!!!
而维护前缀和这种事情,树状数组最在行了
可以写出代码:
1 | int n, a[MAXN], bit[MAXN]; |
区间加减、区间和查询
线段树天下第一
但是线段树难写、难调,常数还大,占空间还多。。。
如果你只需要区间加减、区间和查询,树状数组无疑是你最好的选择
区间加减维护一下差分数组就行了
考虑区间和本质是
计算一下每个 $d_i$ 被算的次数,顺便把式子变换一下
1 | 举个例子 |
拆一下 $\sum$,可以变换成
这样的话,只需要分别维护两个差分数组,一个记 $d_a$,一个记 $d_a \times a$ 就行
修改$\text{[L,R] + }x$的时候,像上面区间加减、单点查询一样,把 $\text{[L]} + x,\text{[R+1]} - x$(对两个数组进行的修改可以合并到 Modify()
函数中,具体见代码)
查询的时候像上面单点加减、区间和查询一样,是前缀和作差
代码:
1 | // 代码没有经过提交,仅进行了一些小样例测试! |
矩阵操作
一维的操作都讲完了,那能不能把它推广到二维上面呢?答案是肯定的。
提前说一句,以下操作从访问$n$个元素变成了$nm$个元素,时间复杂度变为$O(\log(nm))$
单点加减、子矩阵和查询
前面说过,树状数组是利用前缀和的思想进行实现的,既然二维也有前缀和,何不照葫芦画瓢把而为树状数组搞出来呢?
先来复习一下。
为了方便,定义
直观来看,
定义$\text{Sum}(a,b,c,d)$为以$(a,b)$为左下角,$(c,d)$为右上角(对于矩阵是反着的)的矩阵元素之和,那么很显然能看出 $\text{Sum}(5,4,7,5)=\text{Sum}(1,1,7,5)-\text{Sum}(1,1,7,3)-\text{Sum}(1,1,4,5)+\text{Sum}(1,1,4,3)$,也就是四边形$\text{ABCD}-\text{ABGI}-\text{AHFD}+\text{AHEI}$元素的值
二维树状数组和一位的除了多了一维之外没多大区别,手法从一维前缀和换到了二维前缀和
看代码就知道了
1 | // 代码没有经过提交,仅进行了一些小样例测试! |
子矩阵加减、单点查询
还记得区间加减、单点查询吗?
接下来把它推广到二维!
查询手法一样的,二维前缀和
如何修改$(x_1,y_1)\text{ to }(x_2,y_2)$?
先说结论:
$d[x_1][y_1] + x,d[x_1][y_2+1]-x,d[x_2+1][y_1]-x,d[x_2+1][y_2+1]+x$
直观理解:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18下标从 1 开始
1 2 3 4 5
1 0 0 0 0 0
2 0 0 0 0 0
3 0 0 0 0 0
4 0 0 0 0 0
修改(1,2)->(4,3) + x
1 2 3 4 5
1 0 0 0 0 0
2 x 0 0 0 -x
3 0 0 0 0 0
4 -x 0 0 0 x
前缀和:
1 2 3 4 5
1 0 0 0 0 0
2 x x x x 0
3 x x x x 0
4 0 0 0 0 0
放代码
1 | // 代码没有经过提交,仅进行了一些小样例测试! |
子矩阵加减、子矩阵和查询
最后一种操作,也是最难的操作
……其实并不难,如果你把前面都学懂了。
和区间加减、区间和查询一样,先看看查询操作的本质
先统计一下 $d[i][j]$ 被访问了多少次,然后稍微整理一下式子,变成
所以,实现区修区查需要维护四个差分数组!
- 第一个:维护$d[i][j]$
- 第二个:维护$d[i][j]\times i$
- 第三个:维护$d[i][j]\times j$
- 第四个:维护$d[i][j]\times i\times j$
接下来是完整代码:
1 | // |