权值线段树与Kth

· · 个人记录

0.前言

你打开了一道题：

一个长为 n 的序列 A，进行 n 次单点修改或查询第k小数字的操作。

经典的全局第k小问题，平衡树、树状数组、线段树都可以轻松维护。

题目要求强制在线，且 n\leq 10^6。

树状数组只能离线，而平衡树常数巨大。于是你只能望向线段树 ....

1.权值线段树

线段树，它是一个维护区间强有力的工具。权值线段树是一个普通线段树的应用，相当于是开了一个桶，每一个叶子节点装的信息是权值等于该点的个数。对于每一个节点内装的都是该范围有多少个数，底层原理就是线段树的单点修改和区间查询了。考虑到线段树的结构就是二分区间，我们每次查找kth的时候其实就是查找第一个前缀和大于等于k的数字。

比如下面这张图，表示的是这个序列： \{3,1,2,2\} 。可以看出来，单次查找 kth 的每一步都是固定的，可以往下走，那么单次查询的复杂度和树高同阶，也就是 \text{logn} 了。

但是，当前的问题的值域是 \left[1,10^{18}\right]，而权值树的叶节点数量要等于这个长度，怎么办 ？这就要用到线段树的各种令人惊叹的操作了。

动态开点

这应该是线段树最为精妙的思想了。很多时候线段树中并不是每一个点都能用到，权值树中更是有大把的空节点，如果每一个都要占用内存，太浪费了。

使用了动态开点，我们不需要建树，每一次的加或者减都会最多创造出 \text{logn} 个节点，可以有效的节省空间。实现也特别简单，如果当前节点编号u为0，u=++cnt 就好了。

如果是上面那个序列，维护后大概的形状长这样：

可持久化操作

可持久化的权值线段树，也就是主席树，也是一个省空间的技巧。以单点修改为例子，如果我们此时需要添加一个权值进去，需要更新的节点为 \text{logn} 个。也就是说，其余的节点可以全部保留。每一次操作我们都可以生成一个新的符合当前版本的线段树，根节点使用一个数组记录就好了。

大概的形状长这样：

有了这两个操作，相信例题就不在话下了，但是我们要思考一下，为什么线段树（这里是权值线段树）可以支持这样的操作？

answer : 权值线段树结构的统一性

什么叫统一性？也就是说，任意两颗权值线段树的形态是一样的，都是根据区间进行划分的，每一个位置所包含的信息是一个东西。任意两棵树的任意相同位置所代表的节点都是维护一个值。

因此，权值线段树具有 可加减性 ，这代表这权值线段树可以完成前缀累加或者是差分等一系列操作。这些都是平衡树比不了的，因此权值线段树的应用范围更广，而且思路更加巧妙，像数字一样满足结合律与交换律。

比如线段树合并/分裂、树套树，或者是实际应用上的扫描线、逆序对，最重要的也就是本文所提到的 \text{Kth} 了。

2.\text{Kth}问题

先从一般情况的入手，即带修改的情况。

例 1

P3380 【模板】二逼平衡树

一个长为 n 的序列 A，有 n 个单点修改或者是查询给定区间\left[L_i,R_i\right] 的第k小数字的操作。

我们刚刚分析的是全局情况，也就是不需要维护这些数字一开始的位置，只需要往一个权值树里面加就好了。但是现在题目要求我们只求一段区间的，难道每次问一次我们都要重新把这些数字添加进去吗？

显然不是，但是如果我们使用一种方法，让我们可以高效率的找到很多颗权值线段树，使他们的并集可以表示出原有区间的所有数字（注意这里用到了权值线段树的可加性），那么每次查询的时候直接加就好了。对于修改操作，我们每次找到包含了该节点的线段树直接改就好了。这要如何实现呢？

你或许会说，树套树！没错，但是树套树是如何实现的？（我们这里使用树状数组套权值线段树解释）

我们知道，树状数组可以在把 f\left(l,r\right) 分解成 f\left(1,r\right)-f\left(1,l-1\right) 时发挥巨大的作用，可以快速查区间和。而我们这里的问题不是一样的吗？假如把每一颗权值线段树当成一个数字，我们就可以快速填充每一颗权值线段树了。

如图，这是树状数组的形态。我们只需要将平常的数字累加换成权值线段树累加就好了，对应的区间就是权值线段树中包含数字的范围。

空间复杂度：n 个数字，每次加入为 \text{logn} 次，一个数字一共加入 \text{logn} 次， 也就是 O(n\log^2n) 。

时间复杂度：n 次询问，一个区间分为 \text{logn} 颗树，每次询问为 \text{logn} 次递归 ，也就是 O(n\log^2n) 。

如果是特殊情况即静态区间第k小呢，能不能优化一点时空？

例 2

P3834 【模板】可持久化线段树 2

一个长为 n 的序列 A，有 n 次查询给定区间\left[L_i,R_i\right] 的第k小数字。

如果说我们在一般不带修改问题中，为了快速获取一段区间，最快的结构是什么？答案呼之欲出 ------ 前缀和 。

也就是说，前缀和可以 O(1) 分割出我们想要的目标区间，而上述 例 1 使用树状数组是为了要修改。但是，前缀和所添加的数字是 n^2 级别的，空间复杂度不得爆炸？但是别忘了，咱们有可持久化线段树 （主席树） 。

这样一来，主席树可以完美契合前缀和的思想，每次\text{insert}一个数字都可以直接继承上一个版本，空间/时间复杂度达到最小的O(n\log n)，这也是为什么大家都说这是主席树最经典的应用。

例 3

咱们来一点不一样的题目

P2633 Count on a tree

树上静态链上第k小，数据范围 10^5 。 参考代码

既然是区间第k小，咱们也来考虑把 例 2 的思想转移过来。咱们也考虑使用主席树预处理出每一颗树，然后再相减转移。考虑树上差分，设 Sum_i 为 i 到根节点路径上的和，即

树上两点 a,b 最短路径和 = Sum_a+Sum_b-Sum_{LCA}-Sum_{Fa[LCA]} 。

于是这道题写一个树剖求 LCA ，主席树维护值域就好了，记得离散化。我们再拓展一下，如果要求的是子树中的第k小呢？这应该比较简单，维护dfs序的前缀和就好了，把树转换成序列。

小结

因为 例 1 需要修改，所以我们使用了树状数组作为外层结构，而内层使用权值线段树契合。

因为 例 2 是完全静态的，所以我们想到了前缀和作为外层结构，内层结构使用可以和前缀和完全契合的可持久化权值线段树。

而 例 3 , 则充分的体现了权值线段树的 可加减性 ，让差分解决了问题，属于是 例 2 的扩展。

3.一些习题

P1903 [国家集训队] 数颜色 / 维护队列

维护的东西开始不一样了，仔细考虑一下吧。