可持久化数据结构 理论

一、可持久化数据结构简介

可持久化数据结构(Persistent data structure)总是可以保留每一个历史版本，并且支持操作的不可改变性(immutable)。

二、可持久化分类

1.部分可持久化 (Partially Persistent)

所有的版本均可访问，但是只有最新版本可以修改

2.完全可持久化 (Fully Persistent)

所有版本均可即访问又修改。

若支持将两个历史版本合并，则又称为汇合可持久化 (Confluently Persistent)。

三、实际应用

1.几何计算

在几何计算中有许多离线算法，例如悬线扫描法，其基本策略是一次扫描后给出所有询问的回答，在时间复杂度分析相当优秀。但在强迫在线的情况下，每次都要进行一次悬线扫描，询问操作的时间复杂度就从对数时间降为线性。

为了解决时间复杂度上的问题，在这里可以引入可持久化的思维。我们将扫描线的时间轴作为一个变动依据，持久化相关的结构，只要我们能将询问在对数时间内穿梭于这个时间轴，必能动态解决先前的问题。

2.字串处理

为了达到非常高效率的合并操作，防止大量重复性字串的生成伴随的效能退化，使得各方面的操作都能远低于线性操作。如C++中的rope就是一个可持久化的数据结构。不只是字串操作。若处理类型有大量重复操作，均可以考虑将数据结构进行可持久化处理，以达到压缩时间开支的效果。

3.版本回溯

实际上就是对应大部分的应用软体中的redo/undo。如果资料库/操作变动为了高效率操作而会配上复杂的结构（并不像 hash, set 反转操作只需要常数或对数时间），那么为了快速回推变动结果，持久化结构就是要减少 redo/undo 的花费。

资料库本身可以常数回推，纪录变动的部分情况即可。而应用层的计算，大部分实作都是砍掉快取，并且重新计算出一份新的结构，有时候回推的变动大小为 m，为了重新计算结构而消耗了 ，如果 和

4.函数式编程

函数式编程关心类型（代数结构）之间的关系，命令式编程关心解决问题的步骤

函数式编程需要特别的数据结构以符合语言特性，其中不可变的性质更为重要，以利于并行环境与除错。如面向对象编程的 Java 8 后引入 stream 类，支援写出函数式的语法设计，可提供惰性求值、无限值域等的特殊功能。

四、几种常见的可持久化数据结构

1.可持久化线段树

2.可持久化块状数组

3.可持久化平衡树

4.可持久化字典树

5.可持久化可并堆