我们该如何保存线段树的历史版本呢？
众所周知，普通线段树有 \log n 层。以单点加为例，当我们对一个叶子节点进行单点加时，需要同时修改从它到根节点这条链上的所有节点的和，即修改 \log n 个节点。咦？我们只需要修改 \log n 个节点！当我们对一个节点的左子节点修改的时候，右子节点保持原来的信息；当我们对一个节点的右子节点修改的时候，左子节点保持原来的信息。这就意味着，我们完全可以复制我们要修改节点的历史版本。假如我们要修改节点 A 的左子树的信息，先新建节点，将节点 A 的信息复制一份，称作节点 B，则节点 B 的右子节点就是 A 的右子节点，不发生改变；节点 B 的左子节点需要修改，那再新建一个节点 C，并将修改操作下传到 C，并在下传的同时传递节点 A 的左子节点的编号，以供 C 复制。
可以发现，我们每次只修改一条链，只新增了 \log n 个节点。那么最后新建的节点数只有 m\log n 个，其中 m 为版本数。
至于查询操作，不难，直接像普通线段树那样查即可。
代码实现注意
左右子节点的编号不再通过计算得到，而是将左右子节点的编号存储为节点的信息。
同时，普通线段树的空间为 4n，但因为我们的节点数是 (n+m)\log n （初始版本也算），所以要多开，一般是左移 5 位。
如何实现查询静态区间第 k 小
对于 [1,r] 区间的第 k 小，可以建权值线段树，每个节点代表一个权值范围，并记录这个范围内值的个数。查询时，利用线段树二分的思想，记左子树的数的个数为 x，当 k\le x 时，查询左子树的第 k 小；当 k> x 时，查询右子树的第 k-x 小。
接下来就是可持久化线段树的精髓。我们按照输入的顺序，每次插入一个数，作为一个版本。第 i 个版本的意义就是前 i 个数在权值线段树上的分布情况。而虽然每个版本的信息不同，但线段树的结构是完全一样的，每个点代表的也是相同的权值范围。所以，我们利用前缀和思想，假如节点 v 保存的是数值位于 [x,y] 的值的个数，我们用第 r 个版本的节点 v 的信息减去第 l-1 个版本的节点 v 的信息，就是 [l,r] 区间内，数值位于 [x,y] 区间内的数的个数了。在查询时，两个版本同步搜索，就可以进行相减并比较了。
至此，我们已经完成了查询静态区间第 k 小的操作。