可持久化线段树

注意，它的全称为可持久化权值线段树。

例题 \(1\)：可持久化线段树 2

首先我们考虑几个暴力：

对于每次询问，找出区间中的所有数，直接排序求第 \(k\) 小。这样做的时间复杂度为 \(O(nq\log n)\) 的。

对于每次询问，建出一棵权值线段树，然后权值线段树上二分查找即可。

发现瓶颈在于建树，如果忽略建树则复杂度为 \(O(q\log n)\) 的。

我们把每次插入一个数后看做一个历史版本，那么区间 \([l,r]\) 内的数就是 \(r\) 历史版本与 \(l-1\) 历史版本做差。这就是我们的询问。

考虑每次插入一个数改变了什么，改变了一条链上的信息，链最长不过树高，树高为 \(\log n\)，所以每次插入一个数是 \(O(\log n)\) 的，建树总时间复杂度 \(O(n\log n)\)。

查询的时候，因为做了前缀和，所以我们考虑左子树内的数的数量是否不小于当前的\(k\)，如果是，递归左子树；否则递归右子树，同时 \(k\) 减去左子树内数的数量，查询最后会返回这个被离散化后的值，还原一下即可。