可持久化数据结构（二）

引言

本文上接《可持久化数据结构（一）》，简单介绍了动态主席树。然后主要讲解了各类求第 K 小值的算法。

权值线段树的运算

仍然是主席树的部分，我们先系统讲解权值线段树的运算

考虑两颗结构相同的权值线段树 ，那么定义有如下运算：

• 加法： 表示对应结点的 相加得到的权值线段树
• 减法： 表示对应结点的 相减得到的权值线段树
• 数乘：对于整数， 表示对应结点的 cnt 乘 得到的权值线段树

对于上述 ，我们显然不需要建立这颗权值线段树，只需要在 上维护对应的结点，实时计算 即可，那么在这颗线段树上操作的复杂度则为 ；

同理，不过因为只有一颗树，操作复杂度为 .

再举个例子，对于线段树：

它的操作复杂度则为 .（可以理解为常数为 ）

在主席树上，减法的实际意义是区间的 .

那么查询自然就是 的复杂度。

动态主席树

也就是带修改查询区间第 k 小

权值线段树上修改

首先明确修改操作的在权值线段树上的实现

把 改为 ，即相当于把包含 的值域区间的 减 1，把包含 的值域区间的 加 1.

那么对于可持久化权值线段树（主席树）呢

主席树的历史版本维护的是前缀区间对应的权值线段树，如果修改了一个位置 上的值，会导致包含 的前缀区间对应的权值线段树跟着被修改，换言之版本 的权值线段树都要修改才行

树状数组套可持久化权值线段树

我们考虑静态主席树的本质，在初始化的时候，每次上历史版本的基础上新建结点，构建当前版本的线段树

这其实就是一个前缀求和的过程啊

结合权值线段树的加法运算，我们发现每一次在权值线段树上增加一个数，相当于把 个结点的 加 1，换言之这就是权值线段树的加法运算，可以视为权值线段树的前缀和

对于动态主席树，一次修改会导致 的权值线段树被修改，复杂度是 的

那么如果我们用树状数组维护前缀和呢？

那么查询版本 的权值线段树，相当于是 个权值线段树的和

根据权值线段树的运算，对于一次区间查询，复杂度为 .（实现的时候可能要用一个外部数组实现同步跳点）

对于修改操作，也只需要修改 棵线段树，复杂度 .

强制在线

也就是不让你离散化。其实没什么问题，不初始化即可。

访问的时候边访问边建点

对于 的值域最多遍历 个结点，没什么问题

区间第 k 小的传统算法

之前在（一）中讲了主席树的方法了，这里补充一些更古老的算法

无修改

离线

那这就是一道经典的整体二分的题目。就不细讲了

在线

考虑二分答案，问题转化为求区间比 mid 小的数。这个问题有两种处理方法

线段树

按下标建一个线段树，每个点到根的路径上做标记。对每个结点的标记排序。查询的区间被分成 log 个点，每个点 lower bound 查询，算上二分总复杂度 .

分块

令分块大小为 T . 做一下预处理：对每个整块排序，复杂度 。 查询的时侯，对 个整块直接做 lower bound 查询，复杂度 ，对零散的直接扫一遍，复杂度 . 因此查询一次的总复杂度是 .

取 ，可得总复杂度为 .

有修改

离线

也可以整体二分。可以用树状数组维护修改，也可以再用分治法。

在线

同样二分答案，问题转化为求区间比 mid 小的数。

线段树套平衡树

考虑维护线段树，往上面加标记。这时那么每个结点维护的标记会变化，于是每个结点维护一棵平衡树即可，算上二分，查询复杂度 . 修改复杂度 .

分块

带修改的话同样可以分块。修改时直接重新排序。（分块大小应该和上文的不太一样）

权值线段树套平衡树

权值线段树套平衡树，即线段树维护权值，而平衡树维护在该值域区间下的下标。即把值域当区间，下标当标记。然后在树上查询标记个数即可。这个的复杂度是 的。修改的复杂度也是 .

可持久化区间第 k 小

支持在历史版本里修改 / 查询区间第 k 小

带修改操作（直接修改，不是在历史版本上修改），并在历史版本查询区间第 k 小。之前的树状数组套可持久化权值线段树只能查询当前状态下的区间第 k 小。这个问题不用主席树，用线段树套可持久化权值线段树就行（滑稽）

具体定义如下，对于要维护的序列 ，对 的下标开一个线段树，那么对于其中的结点 ，假设它对应的区间 ，即对应序列 ，再在这个结点上开一个基于 的可持久化权值线段树（主席树）

查询

显然，询问区间 可以被分为 个区间，每个区间对应一个结点上的权值线段树，那么同步跳点，复杂度 .

修改

修改一个位置 的值，会把 在线段树上对应的结点到根结点上的权值线段树都 修改一遍，总复杂度为 . 对于新建结点上的权值线段树，继承自原结点的权值线段树。

树上路径第 k 小

给一颗加权树，每次询问 到 路径上的第 k 小边权

静态查询

之前的可持久化权值线段树都是建立在线性区间上的。那么考虑到权值线段树极其优秀以铸就其毒瘤的运算律，我们尝试在树形结构上建立主席树

对于根结点到 这条路径上的边权序列，建立权值线段树.

显然 的权值线段树可以通过父结点的权值线段树持久化得到，那么就能在 的时间内完成初始化。

而路径 可以由两部分得到：.

那么对于这两段，分别用权值线段树的减法就能得到对应路径的线段树，再相加即为 对应的线段树，即 .

那么在权值线段树 上查询第 小即可，时间复杂度 .

动态查询

即带修改操作的查询

对于一类不改变树结构的修改，可以转化为在 DFS 序列上的修改

对于一条边的修改，会影响其子树结点 的 . 那么放在 DFS 序列上就是一段区间的修改

因此我们用线段树维护 DFS 序列上的区间，对每个区间套一个可持久化权值线段树

参考文献

[1]. 陈立杰 . 可持久化数据结构研究 .