可持久化线段树学习笔记

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

线段树

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

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

可持久化?

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

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

可持久化的思路

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

一种非常简单的思路:为了维护修改之前的信息,每次修改我重新建一棵线段树不就好了???但是如果仔细想一想,建一棵线段树的时间复杂度是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数目的节点,这个很容易忘记。我们还需要显性的记录每个节点的左儿子和右儿子,和一些其他你要维护的信息。

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

具体来说如下:

  1. 复制原来节点,成为一个新的当前节点
  2. 往需要更改的位置(左/右儿子)更新

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

查询操作就一模一样啦。

应用

非常强大。

可持久化数组、并查集

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

主席树

静态第k大问题

动态第k大问题

树上第k大、维护值域

其他奇怪应用

例题

TBD。