树状数组
引入
树状数组是一种支持 单点修改 和 区间查询 的,代码量小的数据结构。
什么是「单点修改」和「区间查询」?
假设有这样一道题:
已知一个数列
- 给定
,将 自增 。 - 给定
,求解 的和。
其中第一种操作就是「单点修改」,第二种操作就是「区间查询」。
类似地,还有:「区间修改」、「单点查询」。它们分别的一个例子如下:
- 区间修改:给定
,将 中的每个数都分别自增 ; - 单点查询:给定
,求解 的值。
注意到,区间问题一般严格强于单点问题,因为对单点的操作相当于对一个长度为
普通树状数组维护的信息及运算要满足 结合律 且 可差分,如加法(和)、乘法(积)、异或等。
- 结合律:
,其中 是一个二元运算符。 - 可差分:具有逆运算的运算,即已知
和 可以求出 。
需要注意的是:
- 模意义下的乘法若要可差分,需保证每个数都存在逆元(模数为质数时一定存在);
- 例如
, 这些信息不可差分,所以不能用普通树状数组处理,但是:- 使用两个树状数组可以用于处理区间最值,见 Efficient Range Minimum Queries using Binary Indexed Trees。
- 本页面也会介绍一种支持不可差分信息查询的,
时间复杂度的拓展树状数组。
事实上,树状数组能解决的问题是线段树能解决的问题的子集:树状数组能做的,线段树一定能做;线段树能做的,树状数组不一定可以。然而,树状数组的代码要远比线段树短,时间效率常数也更小,因此仍有学习价值。
有时,在差分数组和辅助数组的帮助下,树状数组还可解决更强的 区间加单点值 和 区间加区间和 问题。
树状数组
初步感受
先来举个例子:我们想知道
一种做法是:
但是如果已知三个数
这就是树状数组能快速求解信息的原因:我们总能将一段前缀
于是,我们只需合并这
不难发现信息必须满足结合律,否则就不能像上面这样合并了。
下面这张图展示了树状数组的工作原理:
最下面的八个方块代表原始数据数组
例如,从图中可以看出:
管辖的是 ; 管辖的是 ; 管辖的是 ; 管辖的是 ;- 剩下的
管辖的都是 自己(可以看做 的长度为 的小区间)。
不难发现,
举例:计算
过程:从
我们刚刚找到的
举例:计算
我们还是从
那不妨考虑最开始,就将查询
管辖区间
那么问题来了,
树状数组中,规定
- 设二进制最低位为第
位,则 恰好为 二进制表示中,最低位的1
所在的二进制位数; ( 的管辖区间长度)恰好为 二进制表示中,最低位的1
以及后面所有0
组成的数。
举个例子,
因为 1
以及后面的 0
组成的二进制是 1000
,即
因此,
我们记 1
以及后面的 0
组成的数为
这里注意:1
所在的位数 1
和后面所有 0
组成的
怎么计算 lowbit
?根据位运算知识,可以得到 lowbit(x) = x & -x
。
lowbit 的原理
将 x
的二进制所有位全部取反,再加 1,就可以得到 -x
的二进制编码。例如,110
,全部取反后得到 001
,加 1
得到 010
。
设原先 x
的二进制编码是 (...)10...00
,全部取反后得到 [...]01...11
,加 1
后得到 [...]10...00
,也就是 -x
的二进制编码了。这里 x
二进制表示中第一个 1
是 x
最低位的 1
。
(...)
和 [...]
中省略号的每一位分别相反,所以 x & -x = (...)10...00 & [...]10...00 = 10...00
,得到的结果就是 lowbit
。
实现
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 |
|
区间查询
接下来我们来看树状数组具体的操作实现,先来看区间查询。
回顾查询
其实任何一个区间查询都可以这么做:查询
事实上,将有关
那前缀查询怎么做呢?回顾下查询
从
往前跳,发现 只管辖 这个元素;然后找 ,发现 管辖的是 ,然后跳到 ,发现 管辖的是 这些元素,然后再试图跳到 ,但事实上 不存在,不跳了。 我们刚刚找到的
是 ,事实上这就是 拆分出的三个小区间,合并一下,答案是 。
观察上面的过程,每次往前跳,一定是跳到现区间的左端点的左一位,作为新区间的右端点,这样才能将前缀不重不漏地拆分。比如现在
我们可以写出查询
- 从
开始往前跳,有 管辖 ; - 令
,如果 说明已经跳到尽头了,终止循环;否则回到第一步。 - 将跳到的
合并。
实现时,我们不一定要先把
比如我们要维护的信息是和,直接令初始
实现
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 |
|
树状数组与其树形态的性质
在讲解单点修改之前,先讲解树状数组的一些基本性质,以及其树形态来源,这有助于更好理解树状数组的单点修改。
我们约定:
。即, 是 管辖范围的左端点。- 对于任意正整数
,总能将 表示成 的形式,其中 。 - 下面「
和 不交」指 的管辖范围和 的管辖范围不相交,即 和 不相交。「 包含于 」等表述同理。
性质
证明
证明:假设
将
不难发现
所以
所以,如果
性质
证明
证明:设
不难发现
所以,
性质
证明
证明:设
不难发现
因此
所以,
有了这三条性质的铺垫,我们接下来看树状数组的树形态(请忽略
事实上,树状数组的树形态是
注意,在考虑树状数组的树形态时,我们不考虑树状数组大小的影响,即我们认为这是一棵无限大的树,方便分析。实际实现时,我们只需用到
这棵树天然满足了很多美好性质,下面列举若干(设
。 大于任何一个 的后代,小于任何一个 的祖先。- 点
的 严格小于 的 。
证明
设
- 点
的高度是 ,即 二进制最低位1
的位数。
高度的定义
点
也就是说,一个点的高度恰好比它最高的那个儿子再高
这里引出高度这一概念,是为后面解释复杂度更方便。
真包含于 (性质 )。 真包含于 ,其中 是 的任一祖先(在上一条性质上归纳)。 真包含 ,其中 是 的任一后代(上面那条性质 , 颠倒)。- 对于任意
,若 不是 的祖先,则 和 不交。
证明
- 对于任意
,如果 不在 的子树上,则 和 不交(上面那条性质 , 颠倒)。 - 对于任意
,当且仅当 是 的祖先, 真包含于 (上面几条性质的总结)。这就是树状数组单点修改的核心原理。 - 设
,则其儿子数量为 ,编号分别为 。- 举例:假设
, 的二进制编号为...1000
,则 有三个儿子,二进制编号分别为...0111
、...0110
、...0100
。
- 举例:假设
证明
在一个数
考虑
考虑
考虑
考虑
的所有儿子对应 的管辖区间恰好拼接成 。- 举例:假设
, 的二进制编号为...1000
,则 有三个儿子,二进制编号分别为...0111
、...0110
、...0100
。 c[...0100]
表示a[...0001 ~ ...0100]
。c[...0110]
表示a[...0101 ~ ...0110]
。c[...0111]
表示a[...0111 ~ ...0111]
。- 不难发现上面是三个管辖区间的并集恰好是
a[...0001 ~ ...0111]
,即 。
- 举例:假设
证明
不难发现
考虑相邻的两个儿子
考虑最左面的儿子
考虑最右面的儿子
因此,这些儿子的管辖区间可以恰好拼成
单点修改
现在来考虑如何单点修改
我们的目标是快速正确地维护
管辖
设
- 初始令
。 - 修改
。 - 令
,如果 说明已经跳到尽头了,终止循环;否则回到第二步。
区间信息和单点修改的种类,共同决定
- 若
维护区间和,修改种类是将 加上 ,则修改方式则是将所有 也加上 。 - 若
维护区间积,修改种类是将 乘上 ,则修改方式则是将所有 也乘上 。
然而,单点修改的自由性使得修改的种类和维护的信息不一定是同种运算,比如,若
下面以维护区间和,单点加为例给出实现。
实现
1 2 3 4 5 6 |
|
1 2 3 4 |
|
建树
也就是根据最开始给出的序列,将树状数组建出来(
一般可以直接转化为
比如给定序列
也有
复杂度分析
空间复杂度显然
时间复杂度:
- 对于区间查询操作:整个
的迭代过程,可看做将 二进制中的所有 ,从低位到高位逐渐改成 的过程,拆分出的区间数等于 二进制中 的数量(即 )。因此,单次查询时间复杂度是 ; - 对于单点修改操作:跳父亲时,访问到的高度一直严格增加,且始终有
。由于点 的高度是 ,所以跳到的高度不会超过 ,所以访问到的 的数量是 级别。因此,单次单点修改复杂度是 。
区间加区间和
前置知识:前缀和 & 差分。
该问题可以使用两个树状数组维护差分数组解决。
考虑序列
一样地,我们考虑将查询区间和通过差分转化为查询前缀和。那么考虑查询
观察这个式子,不难发现每个
那么怎么做区间加呢?考虑给原数组
因为差分是
多了 而 不变,所以 的值多了 。 不变而 多了 ,所以 的值少了 。- 对于不等于
且不等于 的任意 , 和 要么都没发生变化,要么都加了 , 还是 ,所以其它的 均不变。
那就不难想到维护方式了:对于维护
而更弱的问题,「区间加求单点值」,只需用树状数组维护一个差分数组
这里直接给出「区间加区间和」的代码:
实现
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 29 30 |
|
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 |
|
根据这个原理,应该可以实现「区间乘区间积」,「区间异或一个数,求区间异或值」等,只要满足维护的信息和区间操作是同种运算即可,感兴趣的读者可以自己尝试。
二维树状数组
单点修改,子矩阵查询
二维树状数组,也被称作树状数组套树状数组,用来维护二维数组上的单点修改和前缀信息问题。
与一维树状数组类似,我们用
对于单点修改,设:
即
则只有
正确性证明
考虑一个大小为
则命题等价为:
也就是说,在树状数组树形态上,
所以
对于查询,我们设:
则合并所有
正确性证明
设
考虑一个一维树状数组
类似地,设
又类似地,就有
其实这里
下面给出单点加、查询子矩阵和的代码。
实现
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
子矩阵加,求子矩阵和
和一维树状数组的「区间加区间和」问题类似,考虑维护差分数组。
二维数组上的差分数组是这样的:
为什么这么定义?
这是因为,理想规定状态下,在差分矩阵上做二维前缀和应该得到原矩阵,因为这是一对逆运算。
二维前缀和的公式是这样的:
所以,设
移项就得到二维差分的公式了。
这样以来,对左上角
至于原因,把这四个
举个例子吧,初始差分数组为
(其中
因此,子矩阵加的做法是:转化为差分数组上的四个单点加操作。
现在考虑查询子矩阵和:
对于点
原因就是差分的前缀和的前缀和就是原本的前缀和。
和一维树状数组的「区间加区间和」问题类似,统计
然后接着推导:
所以我们需维护四个树状数组,分别维护
当然了,和一维同理,如果只需要子矩阵加求单点值,维护一个差分数组然后询问前缀和就足够了。
下面给出代码:
实现
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 29 30 31 32 33 |
|
权值树状数组及应用
我们知道,普通树状数组直接在原序列的基础上构建,
然而事实上,我们还可以在原序列的权值数组上构建树状数组,这就是权值树状数组。
什么是权值数组?
一个序列
例如:
很明显,
若原数列值域过大,且重要的不是具体值而是值与值之间的相对大小关系,常 离散化 原数组后再建立权值数组。
另外,权值数组是原数组无序性的一种表示:它重点描述数组的元素内容,忽略了数组的顺序,若两数组只是顺序不同,所含内容一致,则它们的权值数组相同。
因此,对于给定数组的顺序不影响答案的问题,在权值数组的基础上思考一般更直观,比如 [NOIP2021] 数列。
运用权值树状数组,我们可以解决一些经典问题。
单点修改,查询全局第 小
在此处只讨论第
该问题可离散化,如果原序列
对于单点修改,只需将对原数列的单点修改转化为对权值数组的单点修改即可。具体来说,原数组
对于查询第
这样做时间复杂度是
考虑用倍增替代二分。
设
- 查询权值数组中
的区间和 。 - 如果
,扩展成功, , ;否则扩展失败,不操作。
这样得到的
看起来这种方法时间效率没有任何改善,但事实上,查询
原因很简单,考虑
如此一来,时间复杂度降低为
实现
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
全局逆序对(全局二维偏序)
相关阅读和参考实现:逆序对
全局逆序对也可以用权值树状数组巧妙解决。问题是这样的:给定长度为
该问题可离散化,如果原序列
我们考虑从
事实上,我们只需要这样做(设当前
- 查询
的前缀和,即为左端点为 的逆序对数量。 自增 ;
原因十分自然:出现在
用例子说明,
,查询 前缀和,为 , 自增 , 。 ,查询 前缀和,为 , 自增 , 。 ,查询 前缀和,为 , 自增 , 。 ,查询 前缀和,为 , 自增 , 。 ,查询 前缀和,为 , 自增 , 。
所以最终答案为
注意到,遍历
- 对
的修改不影响对 的查询。 - 颠倒后,实质是在查询
且 的数对数量,而 时不存在 ,所以 相当于 ,所以这与原来的逆序对问题是等价的。
如果查询非严格逆序对(
- 对
的修改 影响 对 的查询。 - 颠倒后,实质是在查询
且 的数对数量,而 时恒有 ,所以 不相当于 ,与原问题 不等价。
如果查询
另外,对于原逆序对问题,还有一种做法是正着枚举
- 查询
( 是 的大小,即 的值域(或离散化后的值域))的区间和。 - 将
自增 。
原因:出现在
此外,逆序对的计数还可以通过 归并排序 解决。这一方法可以避免离散化。时间复杂度同样为
树状数组维护不可差分信息
比如维护区间最值等。
注意,这种方法虽然码量小,但单点修改和区间查询的时间复杂度均为
区间查询
我们还是基于之前的思路,从
因此,如果我们跳到了
- 如果小于
,我们直接把 单点 合并到总信息里,然后跳到 。 - 如果大于等于
,说明没越界,正常合并 ,然后跳到 即可。
下面以查询区间最大值为例,给出代码:
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
可以证明,上述算法的时间复杂度是
时间复杂度证明
考虑
如果
如果
因此,
单点更新
注
请先理解树状数组树形态的以下两条性质,再学习本节。
- 设
,则其儿子数量为 ,编号分别为 。 的所有儿子对应 的管辖区间恰好拼接成 。
关于这两条性质的含义及证明,都可以在本页面的 树状数组与其树形态的性质 一节找到。
更新
对于最值(以最大值为例),一种常见的错误想法是,如果
事实上,对于不可差分信息,不存在通过
换句话说,对每个受影响的
考虑
实现
1 2 3 4 5 6 7 8 9 10 |
|
容易看出上述算法时间复杂度为
建树
可以考虑拆成
也有
Tricks
建树
以维护区间和为例。
方法一:
每一个节点的值是由所有与自己直接相连的儿子的值求和得到的。因此可以倒着考虑贡献,即每次确定完儿子的值后,用自己的值更新自己的直接父亲。
实现
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 |
|
方法二:
前面讲到
实现
1 2 3 4 5 6 |
|
1 2 3 4 |
|
时间戳优化
对付多组数据很常见的技巧。若每次输入新数据都暴力清空树状数组,就可能会造成超时。因此使用
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
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 |
|
例题
- 树状数组 1:单点修改,区间查询
- 树状数组 2:区间修改,单点查询
- 树状数组 3:区间修改,区间查询
- 二维树状数组 1:单点修改,区间查询
- 二维树状数组 2:区间修改,单点查询
- 二维树状数组 3:区间修改,区间查询
本页面最近更新:2024/11/30 23:16:09,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:ananbaobeichicun, HeRaNO, iamtwz, Ir1d, ouuan, ranwen, shuzhouliu, wangdehu, Xeonacid, Zhoier, aofall, AtomAlpaca, c-forrest, chenryang, Chrogeek, ChungZH, CoelacanthusHex, corchis-S, countercurrent-time, david-why, dbxxx-ac, dbxxx-oi, Early0v0, Enter-tainer, Great-designer, H-J-Granger, ksyx, LiuZengqiang, Marcythm, mcendu, megakite, Menci, NachtgeistW, Nemodontcry, Persdre, RuiYu2021, shawlleyw, sshwy, SukkaW, Suyun514, Tiphereth-A, Weijun-Lin, Ycrpro
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用