树状数组学习笔记
树状数组(Fenwick Tree),这次EC Final遇到过的,英文也记一下,也来学一下,刚好半夜刷题刷到了树状数组可以解决的题目!
简介
树状数组和线段树具有相似的功能,但他俩毕竟还有一些区别:树状数组能有的操作,线段树一定有;线段树有的操作,树状数组不一定有。但是树状数组的代码要比线段树短,思维更清晰,速度也更快,在解决一些单点修改的问题时,树状数组是不二之选。
原理
下面这张图展示了树状数组的工作原理:
这个结构和线段树有些类似:用一个大节点表示一些小节点的信息,进行查询的时候只需要查询一些大节点而不是所有的小节点。
最上面的八个方块就代表数组 \(a\)。
他们下面的参差不齐的剩下的方块就代表数组 \(a\) 的上级——\(c\) 数组。
从图中可以看出:
\(c_2\) 管理的是 \(a_1\),\(a_2\);
\(c_4\) 管理的是 \(a_1\),\(a_2\),\(a_3\),\(a_4\);
\(c_6\) 管理的是 \(a_5\),\(a_6\);\(c_8\) 则管理全部 \(8\) 个数。
如果要计算数组 \(a\) 的区间和,比如说要算 \(a_{51}\)~\(a_{91}\) 的区间和,可以采用类似倍增的思想:
从 \(91\) 开始往前跳,发现 \(c_n\)(\(n\) 我也不确定是多少,算起来太麻烦,就意思一下)只管 \(a_{91}\) 这个点,那么你就会找 \(a_{90}\),发现 \(c_{n - 1}\) 管的是 \(a_{90}\)&\(a_{89}\);那么你就会直接跳到 \(a_{88}\),\(c_{n - 2}\) 就会管 \(a_{81}\)~\(a_{88}\) 这些数,下次查询从 \(a_{80}\) 往前找,以此类推。
用法及操作
那么问题来了,怎么知道 \(c_i\)
管理的数组 \(a\) 中的哪个区间呢?
这时,我们引入一个函数——lowbit
:
1 | // C++ Version |
注释说明了 lowbit
的意思,对于 \(x=88\):\(88_{(10)}=1011000_{(2)}\)
发现第一个 \(1\) 以及他后面的 \(0\) 组成的二进制是 \(1000\)
\(1000_{(2)} = 8_{(10)}\)
\(1000\) 对应的十进制是 \(8\),所以 \(c_{88}\) 一共管理 \(8\) 个 \(a\) 数组中的元素。
在常见的计算机中,有符号数采用补码表示。在补码表示下,数
x
的相反数 -x = ~x + 1
。
使用 lowbit 函数,我们可以实现很多操作,例如单点修改,将 \(a_x\) 加上 \(k\),只需要更新 \(a_x\) 的所有上级:
1 | // C++ Version |
前缀求和:
1 | // C++ Version |
区间加 & 区间求和
若维护序列 \(a\) 的差分数组 \(b\),此时我们对 \(a\) 的一个前缀 \(r\) 求和,即 \(\sum_{i=1}^{r} a_i\),由差分数组定义得 \(a_i=\sum_{j=1}^i b_j\)
进行推导
\[ \begin{aligned} &\sum_{i=1}^{r} a_i\\=&\sum_{i=1}^r\sum_{j=1}^i b_j\\=&\sum_{i=1}^r b_i\times(r-i+1) \\=&\sum_{i=1}^r b_i\times (r+1)-\sum_{i=1}^r b_i\times i \end{aligned} \]
区间和可以用两个前缀和相减得到,因此只需要用两个树状数组分别维护 \(\sum b_i\) 和 \(\sum i \times b_i\),就能实现区间求和。
代码如下
1 | // C++ Version |
Tricks
\(O(n)\) 建树:
每一个节点的值是由所有与自己直接相连的儿子的值求和得到的。因此可以倒着考虑贡献,即每次确定完儿子的值后,用自己的值更新自己的直接父亲。
1 | // C++ Version |
区间加法&单点查询
只要把我们原来维护的数组进行差分即可。这样的话我们原来
get_sum(x)
的操作就会变成查询 x
点的值
,因为我们维护的是差分数组,所以在区间加法的时候我们只需要对端点修改即可,复杂度都是
\(O(log_2n)\)。
以上大部分内容来自 OI WIKI。
例题:CF1679C
题目描述
题目分析
这题题面比较长,但是出的确实比较好。大概就是说给你一张 \(n \times n\) 的棋盘,然后给你 3 种类型的操作。
- 在 \((x,y)\) 中放入一辆车,保证原位置没车
- 在 \((x,y)\) 中取出一辆车 ,保证原位置有车
- 选取一块矩形,由左上角端点坐标和右下角端点坐标描述。让你判断这个矩形区域内是否都在车的攻击范围内。
那么你在没有看到 \(n\times n\) 有范围限制就应该能想到了,这题肯定不能存储棋盘,而要描述车的位置。1,2操作我们可以堪称是单点修改,3操作可以看成是区间查询。那么想到这两点就能很好的想到树状数组了。我们把棋盘横竖分离,横坐标建一棵树状数组,纵坐标也建一棵树状数组,那么在插入 \((x,y)\) 的时候我们就可以对横坐标的 \(x\) 位置进行单点修改,纵坐标的 \(y\) 进行单点修改。其实哪种叫法无所谓,你只要对应上就可以了,不必纠结横纵坐标。那么再仔细解读一下它的第三个要求,判断是否能被车都撞到,那我们很容易想到,横坐标范围都有车或者纵坐标范围都有车,那这个区域都能被车撞到,就可以了,这个区间查询我们查横纵坐标,有一方满足即可。但是需要注意,我们要做一点修改,因为假如一行上面有两辆车,而上一行恰好没有车,那么这两行显然上面那一行不能被撞到,但是因为这两行区间查询得到 \(2\) 我们可能误认为它能撞到这两行,那么这显然不符合逻辑。于是我们可以另外开一个数组记录这一行(列)上面车的数量,给树状数组增加的时候我只用保证这一行(列)之前没有车就行了,同样给树状数组减少的时候我们要确保这一行(列)都没车了,才能减少。这样我们就能愉快地 AC 这题了。
这个题目出的是真的好!
标程
1 |
|
小结
树状数组很后悔没有很早学起来,因为它真的比线段树简单太多了,可惜我是先会的线段树,所以导致就没兴趣学树状数组,不过没事,现在会了也是不迟的!