这个东西几天前就整完了，今天整理一下思路。

首先这里讨论的是可持久化权值线段树。可持久化的普通线段树我不会写，但是我猜思想应该是相同的。
通过将新版本上没有修改的节点接回上一个版本来实现最大限度的重用数据。

区间第k大用可持久化权值线段树的做法如下：

1. 将n个值按照顺序逐个插入树中，产生n个历史版本
2. 对于查询区间[l, r]的第k大值，我们用第r个版本与第l-1个版本的树相减，得到一棵新的树（实际上我们并不需要构造新的树，只需要同时接受两个节点指针，向下查询时算出相减后的节点信息即可），求这棵树上的全区间第k大即为答案

可持久化数据结构的坑应该很大，目前我只看到了一点皮毛，有待更深的研究