有哪些数据结构可以可持久化?

来源：千锋教育

发布人：xqq

时间： 2023-10-16 07:04:26

一、可持久化的数据结构

1.可持久化线段树

对于实现可持久化的方法，我们最容易想到的就是开一个 O(N2) 的空间，把所有版本都存储下来。但这样显然会有很多空间是浪费的，因为相较于被修改的部分来说，两个版本之间完全相同的部分显然会更多。与线性结构相比，树型结构更擅长帮助我们分清楚这两个部分，而树形结构中最擅长处理这种修改查询问题的就是线段树。所以我们先介绍一下利用可持久化线段树实现可持久化数组。

2.可持久化块状数组

回忆线段树的修改流程，我们会发现所有的操作都只跟一条链有关 (下放lazytag是个例外，但也跟一条链差不多) ，因此我们在生成新版本的时候，对于未修改的点可以直接使用旧版本的节点，只有发生修改的点才需要新建一个新节点来代替旧节点，这样空间复杂度就可以降到 O(NlogN) ，而修改查询这些都不会收到影响。

3. 可持久化并查集

写作并查集，前置知识却是利用可持久化线段树实现可持久化数组，过分！回顾并查集，其实不过是一个 fa[a] = b，为了可持久化，我们就用可持久化数组来维护 fa[i]。注意这里不能再使用路径压缩了，道理很简单，可持久化要尽可能减少修改的次数。但是我们依然保留了一种优化方式：在维护 fa[i] 的同时维护一个 dep[i] ，表示这个节点的深度，保证在合并时是深度较小的点向深度较大的点合并即可。

4.可持久化字典树

依旧与可持久化线段树的思想类似，这里的可持久化主要体现在插入新串，这个插入过程影响的节点数量也是O(logN)的，因此插入时像线段树一样生成一个新的链即可。

5.可持久化分块

利用和可持久化线段树相似的思想，将每块都编好序号，用一个 O(√n) 的数组来记录一个版本的所有块。当一个块要被修改时，新建一个值为修改后的块的新块，用一个新数组保存新版本所有的块编号即可。

延伸阅读：

二、可持久化数据结构原理

可持久化：将数据结构的所有历史版本记录下来，称为可持久化。

不是所有的数据结构都是可以持久化的，可持久化的数据结构要求其结构稳定，比如堆（是一颗满二叉树，结构稳定）、树状数组、trie（字典树）、线段树等。平衡树就不可以进行持久化操作，因为其存在左旋、右旋的操作。

存下来所有的历史版本有两种方式，一种是每改动一次则全部备份下来；另一种是增量备份。名列前茅种方式时空复杂度都比较高，不使用这种方式，我们这里只讲解增量备份的方式（类似于git）。

增量备份的核心思想是：只记录每个版本与前一个版本不同的部分。

声明：本站稿件版权均属千锋教育所有，未经许可不得擅自转载。