可持久化线段树

主席树

主席树全称是可持久化权值线段树，参见 知乎讨论。

引入

先引入一道题目：给定 个整数构成的序列 ，将对于指定的闭区间 查询其区间内的第 小值。

你该如何解决？

一种可行的方案是：使用主席树。 主席树的主要思想就是：保存每次插入操作时的历史版本，以便查询区间第 小。

怎么保存呢？简单暴力一点，每次开一棵线段树呗。
那空间还不爆掉？

解释

我们分析一下，发现每次修改操作修改的点的个数是一样的。
（例如下图，修改了 中对应权值为 1 的结点，红色的点即为更改的点）

只更改了 个结点，形成一条链，也就是说每次更改的结点数 = 树的高度。
注意主席树不能使用堆式存储法，就是说不能用 ， 来表示左右儿子，而是应该动态开点，并保存每个节点的左右儿子编号。
所以我们只要在记录左右儿子的基础上，保存插入每个数的时候的根节点就可以实现持久化了。

我们把问题简化一下：每次求 区间内的 小值。
怎么做呢？只需要找到插入 r 时的根节点版本，然后用普通权值线段树（有的叫键值线段树/值域线段树）做就行了。

这个相信大家都能理解，回到原问题——求 区间 小值。
这里我们再联系另外一个知识：前缀和。
这个小东西巧妙运用了区间减法的性质，通过预处理从而达到 回答每个询问。

我们可以发现，主席树统计的信息也满足这个性质。
所以……如果需要得到 的统计信息，只需要用 的信息减去 的信息就行了。

至此，该问题解决！

关于空间问题，我们分析一下：由于我们是动态开点的，所以一棵线段树只会出现 个结点。
然后，有 次修改，每次至多增加 个结点。因此，最坏情况下 次修改后的结点总数会达到 。 此题的 ，单次修改至多增加 个结点，故 次修改后的结点总数为 ，忽略掉 ，大概就是 。

最后给一个忠告：千万不要吝啬空间（大多数题目中空间限制都较为宽松，因此一般不用担心空间超限的问题）！大胆一点，直接上个 ，接近原空间的两倍（即 n << 5）。

实现

拓展：基于主席树的可持久化并查集

主席树是实现可持久化并查集的便捷方式，在此也提供一个基于主席树的可持久化并查集实现示例。

参考

https://en.wikipedia.org/wiki/Persistent_data_structure

https://www.cnblogs.com/zinthos/p/3899565.html