可持久化线段树
主席树
主席树全称是可持久化权值线段树，参见 知乎讨论．
关于函数式线段树
函数式线段树 是指使用函数式编程思想的线段树．在函数式编程思想中，将计算机运算视为数学函数，并避免可改变的状态或变量．不难发现，函数式线段树是 完全可持久化 的．
引入
先引入一道题目：给定 𝑛n
个整数构成的序列 𝑎a，将对于指定的闭区间 [𝑙,𝑟][l,r] 查询其区间内的第 𝑘k 小值．
你该如何解决？
一种可行的方案是：使用主席树． 主席树的主要思想就是：保存每次插入操作时的历史版本，以便查询区间第 𝑘k 小．
怎么保存呢？简单暴力一点，每次开一棵线段树呗． 那空间还不爆掉？
解释
我们分析一下，发现每次修改操作修改的点的个数是一样的． （例如下图，修改了 [1,8][1,8] 中对应权值为 1 的结点，红色的点即为更改的点） 
只更改了 𝑂(log𝑛)O(logn) 个结点，形成一条链，也就是说每次更改的结点数 = 树的高度． 注意主席树不能使用堆式存储法，就是说不能用 𝑥 ×2x×2，𝑥 ×2 +1x×2+1 来表示左右儿子，而是应该动态开点，并保存每个节点的左右儿子编号． 所以我们只要在记录左右儿子的基础上，保存插入每个数的时候的根节点就可以实现持久化了．
我们把问题简化一下：每次求 [1,𝑟][1,r] 区间内的 𝑘k 小值． 怎么做呢？只需要找到插入 r 时的根节点版本，然后用普通权值线段树（有的叫键值线段树/值域线段树）做就行了．
这个相信大家都能理解，回到原问题——求 [𝑙,𝑟][l,r] 区间 𝑘k 小值． 这里我们再联系另外一个知识：前缀和 ． 这个小东西巧妙运用了区间减法的性质，通过预处理从而达到 𝑂(1)O(1) 回答每个询问．
我们可以发现，主席树统计的信息也满足这个性质． 所以……如果需要得到 [𝑙,𝑟][l,r] 的统计信息，只需要用 [1,𝑟][1,r] 的信息减去 [1,𝑙 −1][1,l−1] 的信息就行了．
至此，该问题解决！
关于空间问题，我们分析一下：由于我们是动态开点的，所以一棵线段树只会出现 2𝑛 −12n−1 个结点． 然后，有 𝑛n 次修改，每次至多增加 ⌈log2𝑛⌉ +1⌈log2n⌉+1 个结点．因此，最坏情况下 𝑛n 次修改后的结点总数会达到 2𝑛 −1 +𝑛(⌈log2𝑛⌉ +1)2n−1+n(⌈log2n⌉+1)． 此题的 𝑛 ≤105n≤105，单次修改至多增加 ⌈log2105⌉ +1 =18⌈log2105⌉+1=18 个结点，故 𝑛n 次修改后的结点总数为 2 ×105 −1 +18 ×1052×105−1+18×105，忽略掉 −1−1，大概就是 20 ×10520×105．
最后给一个忠告：千万不要吝啬空间（大多数题目中空间限制都较为宽松，因此一般不用担心空间超限的问题）！大胆一点，直接上个 25 ×10525×105，接近原空间的两倍（即 n << 5）．
实现
---|---
## 拓展：基于主席树的可持久化并查集
主席树是实现可持久化并查集的便捷方式，在此也提供一个基于主席树的可持久化并查集实现示例．
---|---
参考
<https://en.wikipedia.org/wiki/Persistent_data_structure>
<https://www.cnblogs.com/zinthos/p/3899565.html>
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Ir1d, H-J-Granger, StudyingFather, EndlessCheng, Enter-tainer, countercurrent-time, NachtgeistW, cjsoft, Tiphereth-A, abc1763613206, Alpha1022, AngelKitty, CCXXXI, diauweb, Early0v0, ezoixx130, GekkaSaori, Konano, LovelyBuggies, Makkiy, mgt, minghu6, ouuan, P-Y-Y, PotassiumWings, SamZhangQingChuan, sshwy, Suyun514, weiyong1024, billchenchina, ChungZH, FinParker, GavinZhengOI, Gesrua, Honeta, hsfzLZH1, iamtwz, ksyx, kxccc, lychees, Marcythm, Peanut-Tang, renbaoshuo, SukkaW, william-song-shy 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用