可持久化线段树

概述

可持久化线段树 是一种可持久化数据结构。

一般情况下，我们需要修改线段树。但是，有的时候需要查询历史版本，而重新建树显然太慢。这时，我们就需要可持久化线段树。

可持久化线段树与一般的线段树的不同点在于：可持久化线段树在每次修改时，增加一条从根到修改点的链，这条链的长度仅为 $\log n$。因为通过增加链来修改，点 $u$ 的儿子不一定是 $u \times 2$ 和 $u \times 2+1$，需要使用数组存储左右子节点的编号；同时，一个节点可能有不止一个父节点。

可持久化下标线段树

维护一棵线段树，支持如下操作：

在某个历史版本上修改某一个位置上的值；
访问某个历史版本上的某一位置的值。

考虑实现一种可持久化线段树，有三个函数：

build 函数：与一般的线段树基本相同，只不过需要动态开点；
insert 函数：用来插入一个新的值，同时创建一个新的版本；
query 函数：与一般的线段树相同。

void insert(int&rt,int pre,int l,int r,int loc,int value) 的意思是：

rt：当前的节点（新创建的），通过引用传值来赋值（即：rt=++tot;）；
pre：在原树中与当前节点所对应的点；
l：同一般的线段树，表示查询区间的左端点；
r：同一般的线段树，表示查询区间的右端点；
loc：同一般的线段树，表示需要修改的端点；
value：同一般的线段树，表示需要修改的端点将会赋予的值。

可持久化权值线段树

可持久化权值线段树 由黄嘉泰发明，又名主席树。

例题

名称	编号	备注	题解
		可持久化下标线段树的模板题
		可持久化权值线段树的模板题

天天爱射击 / Shooting	TUHPC2017A		提交记录备份
可持久化并查集	Luogu P3402	在可持久化线段树上实现按秩合并的并查集	提交记录备份
任务查询系统	CQOI2015T3		提交记录备份




New Queries On Segment Deluxe	GYM 103439B	支持区间修改区间查询的可持久化线段树，标记永久化，$k \le 4$，可以建立 $2^k$ 个线段树	提交记录备份

例题：树上的可持久化线段树

名称	编号	备注	题解
		DFS 序、树上差分、可持久化权值线段树
森林	SDOI2013R1D1T2	树上主席树，启发式合并，为节省内存空间建议回收删除的节点。时间复杂度为 $O(n \log^2n+t \log n)$，空间复杂度为 $O(n \log n)$。	提交记录备份
		DFS 序，可持久化下标线段树