可持久化线段树学习笔记

可持久化线段树，是一种可以进行可持久化操作的线段树，具有优越的时间复杂度。

线段树

相信看这篇文章的人很熟悉什么是线段树了，就不在这里胡扯了。

如上就是线段树的基本结构。

可持久化？

简单来说，可持久化就是能够在修改的时候，保留下原来的数据结构的样子的一种数据结构。比如说，对于上图，如果线段树维护的是区间和，这个时候我们要修改某个数的大小，就会使一条链上的信息全部改变，并且我们失去了这次修改之前的线段树的信息。

那么对于线段树来说，怎么样才能做到可持久化呢？

可持久化的思路

假设这个线段树维护的是区间和。

一种非常简单的思路：为了维护修改之前的信息，每次修改我重新建一棵线段树不就好了？？？但是如果仔细想一想，建一棵线段树的时间复杂度是O(n)，空间复杂度O(n)，如果有n次修改，最后的时间复杂度O(n^2)，空间复杂度也是O(n^2)，GG。

观察上图，显然可以发现单点修改会改变的只会有这一条链上的节点的值，所以我们就会自然想到，能不能只维护这一条链呢？

但是单独维护一条链很傻，而且很多线段树上的操作进行起来也很复杂。所以可以把这条链嵌到线段树上，比如我们修改位置4，那么修改出来的链就是红色节点，而我们也需要把它其他的地方连到原来的线段树上。

这个时候，我们就发现只要我们掌握着根结点，我们就可以当所有其他线段树都是不存在的一样，做普通线段树的查询操作。

主要的可持久化操作的思想大概如上。总结来说的话，就是只更改需要更改的部分，其他的不管它，保持树形结构完整性就可以了。其他的可持久化数据结构如可持久化Trie树和平衡树，思想都是类似的。

分析一下的话，上例子里总共有m次修改的话，每次修改创建出的新节点都是一条完整的长度为O(\log n)的链，每次修改或者查询，时间复杂度都是O(\log{n})。最后空间复杂度是O(n \log{n})，时间复杂度也是O(n \log{n})。

具体实现

具体来说，可持久化数据结构一般推荐用数组模拟指针来实现。首先是因为数组的代码写起来很短很快，其次还有就是指针的大小目前一般是8字节，比一个整数大了一倍，在一些题目中可能被卡内存。

对于可持久化线段树来说，实现跟普通线段树有微小的一点不同。（废话

首先，在节点的数目上，我们需要开n\log n数目的节点，这个很容易忘记。我们还需要显性的记录每个节点的左儿子和右儿子，和一些其他你要维护的信息。

在修改操作上，有一些不同。

具体来说如下：

复制原来节点，成为一个新的当前节点
往需要更改的位置（左／右儿子）更新

这里的修改中的原来节点就是原来同一个位置的节点，而需要新建一个节点，所以这个地方当前节点需要传一个引用，具体到后面可以看一看代码，理解的会更好。

查询操作就一模一样啦。

应用

非常强大。

可持久化数组、并查集

可持久化数组可以说是最简单的应用了。就是一个模板，套上就好。