前景

可持久化数组在许多地方有广泛的应用:可持久化并查集、支持回退操作的字符串、可持久化数据结构。

准备工作

我们需要对应的头文件和命名空间,这都是标准c++支持的。

rope的原理与基本操作

rope是给予维护深度平衡的可持久化平衡树。每次操作都会新建节点,因此内部是可持久化的。
rope一般用来维护一个支持历史版本查询的字符串。它本身也可以像字符串一样使用。

rope的可持久化

一般,我们可以利用rope底层可持久化的机制,进行O(1)回退。也就是我们只需要回退根节点的版本,我们就可以很顺利地访问当时的所有节点了。故回退复杂度为O(1)
可持久化rope的初始化:

可持久化rope建立新版本和回退旧版本:

一道模板题(Version Controlled IDE-UVa12538)

给定一个字符串,要求支持以下操作:
1 a str 在a位置插入str
2 a b 删除a到b的字符串
3 a b c 输出a版本的b开始的c个字符
输入已经进行加密,请将每个数据的数字减去你已经输出的'c'的个数

又是一道模板题(可持久化并查集-BZOJ3673)

n个集合 m个操作
操作:
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合,是则输出1否则输出0

0<n,m<=2*10^4