前景

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

准备工作

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

#include <ext/rope>
using namespace __gnu_cxx;

rope 的原理与基本操作

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

#include <ext/rope>
using namespace __gnu_cxx;
rope<char> str,x;
str.insert(pos,"abc")//在 pos 位置开始插入"abc"
str.push_back("x")//在末尾追加"x"
str.erase(a,b)//在 a 位置开始删除 b 个
str.replace(a,"abc")//在 a 位置开始用"abc"替换
str.substr(a,b)//返回从 a 位置开始共 b 个的字符串
str.reverse(a,b)//反转 [a,b) 区间，虽然很慢

rope 的可持久化

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

rope<char>*ver[100];
ver[0]=new rope<char>();

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

ver[i]=new rope<char>(*ver[i-1]);//从版本 (i-1) 建立新版本 i
ver[i]=ver[i-1]//版本 i 回退为版本 (i-1)

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

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

#include <iostream>
#include <cstring>
#include <cstdio>
#include <ext/rope>

#define MX 1000001

using namespace std;
using namespace __gnu_cxx;

char str[MX];
rope<char> *rp[50001],tmp;
int ver[MX],num,n,d;

int main()
{
    rp[0]=new rope<char>();
    int op,a,b,c;
    scanf("%d",&n);
    for(register int i=1;i<=n;i++)
    {
        rp[i]=new rope<char>(*rp[i-1]);
        scanf("%d",&op);
        if(op==1)
        {
            ver[++num]=i;
            scanf("%d%s",&a,str);
            rp[i]->insert(a-d,str);
        }
        else if(op==2)
        {
            ver[++num]=i;
            scanf("%d%d",&a,&b);
            rp[i]->erase(a-1-d,b-d);
        }
        else
        {
            scanf("%d%d%d",&a,&b,&c);
            tmp=(rp[ver[a-d]]->substr(b-1-d,c-d));
            d+=count(tmp.begin(), tmp.end(), 'c');
            cout<<tmp<<endl;
        }
    }
    return 0;
}

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

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

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

#include <iostream>
#include <cstring>
#include <cstdio>
#include <ext/rope>

#define MX 20002

using namespace std;
using namespace __gnu_cxx;

rope<int> *fa[MX];
int src[MX];
int n,m;

int findfa(int x,int ver)
{
    if(fa[ver]->at(x)==x)return x;
    else
    {
        fa[ver]->replace(x,findfa(fa[ver]->at(x),ver));
        return fa[ver]->at(x);
    }
}

void comb(int a,int b,int ver)
{
    int f1,f2;
    f1=findfa(a,ver);
    f2=findfa(b,ver);
    fa[ver]->replace(f1,f2);
}

int same(int a,int b,int ver)
{
    int f1,f2;
    f1=findfa(a,ver);
    f2=findfa(b,ver);
    return (f1==f2);
}

int main()
{
    int a,b,o;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)src[i]=i;
    fa[0]=new rope<int>(src,src+n+1);
    for(int i=1;i<=m;i++)
    {
        fa[i]=new rope<int>(*fa[i-1]);
        scanf("%d",&o);
        if(o==1)
        {
            scanf("%d%d",&a,&b);
            comb(a,b,i);
        }
        else if(o==2)
        {
            scanf("%d",&a);
            fa[i]=fa[a];
        }
        else
        {
            scanf("%d%d",&a,&b);
            cout<<same(a,b,i)<<endl;
        }
    }
    return 0;
}