Part 0. 引言

区间第 $k$ 小问题是一个很经典的问题。很明显，区间最值问题应该用线段树解决，但是问题是这里并不是最大值/最小值，而是第 $k$ 个值。这样就意味着，如果我们要对他进行普通线段树的合并，那么就会导致你需要把左右两个区间前 $k$ 个值都找出来，如果 $k=n$ ，那么这个问题的合并复杂度就是 $O(n\log n)$ ，再加上本身的查找复杂度，这个复杂度就变成了 $O(n^2\log^2 n)$ ，还不如暴力呢。

那么，这个问题应该如何解决？他和可持久化线段树又有什么关系？

Part 1. 换个思路

如果普通的线段树行不通的话，我们完全可以另行其道。比如说……我们可以先想一个简单的问题：如果现在不是让你求一个区间，而是从1到某个位置的第 $k$ 小值，你会怎么做？

如果你能想到桶，那么这个问题就好办多了。从1到 $r$ 的区间里，我们给每一个数都做一个桶，这样如果我们要找第 $k$ 小值，就只需要在这个桶上面二分。也就是说，如果左区间那一部分有大于等于 $k$ 个数（注意这里用的是桶，所以这里的区间是桶的区间，而不是原始序列的区间。其实准确地说，是桶的前缀和的区间），我们要找的数就一定在左区间里面的第 $k$ ，反之亦然。也就是说，我们用线段树维护这个桶数组的区间和，如果左区间的和大于 $k$ ，那么就查找左区间第 $k$ 大的，否则就查找右区间第 $k-sum[l]$ 个（注意：不是第 $k$ 个）

这是什么？这不就是权值线段树吗？对的。

问题在于，如果是从 $l$ 到 $r$ 呢？肯定不能再对于每一个起点都搞个桶出来吧？这样肯定会爆空间。

Part 2. 差分思想

我们来想，既然这里我们用桶来解决问题，那么就可以对桶进行相减对不对？举个简单的例子，假如我给定一个这样的序列：

1	1 3 3 7 6 0 3 2 4 3

我们把这个序列放到桶里。当我们把前三个放到桶里以后， $3$ 号元素有 $2$ 个。等到全部放进去之后， $3$ 号元素有 $4$ 个。那就意味着，从第 $4$ 个到第 $10$ 个，就有 $4-2=2$ 个 $3$ 号元素。

既然普通的桶可以相减，那么权值线段树当然也可以，读者可以自行尝试。也就是说，我们只要知道当我们往桶里放了 $l-1$ 个元素和 $r$ 个元素的时候，权值线段树长什么样子，就完全可以推断出区间的 $k$ 小值，依然二分即可。

怎么才能知道当时的线段树长什么样子呢？这就是可持久化线段树的用处了。

Part 3. 可持久化

可持久化，顾名思义，就是能够知道之前的线段树是什么样子的，说得专业一点，就是“可以回退到某一个历史版本”。

比较暴力的想法就是，对于每一个版本建一个新树，然后全都存起来。但是这完全不行啊！一个线段树大概要 $4N$ 的空间，如果再有上一堆版本，空间就直接起飞了。那么怎么解决这个问题呢？答案很简单，增量备份（你们能理解这个梗吗）。因为每一次我们进行添加的时候，只修改了一个值，也就是单点修改，那么更新线段树的时候只会更新这个节点到根节点的这一条 $\log n$ 长度的链。这样，每一次都只新存储这个链，就可以做到优秀的空间复杂度了。

可以参考 OI Wiki 的图进行理解：

另外，这样的话我们就不能堆式存储了，我们要动态开点。同时，还有一个问题，那就是怎样存储版本信息呢？考虑到我们每一次只修改一个点，只需要把每一次修改的点和这一次修改所对应新建的根节点对应起来，剩下的工作直接让他自己完成就行。

这样，这道题就解决了。最后还有一点，就是如果这个数很大，要离散化，不然桶是装不下的。开数组的话，就直接 $2^5N$ 就可以存下。