题解 P3919 【【模板】可持久化数组（可持久化线段树/平衡树）】

· · 题解

貌似没有写非递归版的题解。。。。。。

首先要了解此数据结构的基础——线段树。推荐一下这篇博客，对线段树的基本操作讲得挺详细的。

可持久嘛！就是当出现历史版本的时候，能够非常方便地维护一个区间的历史版本。

自然，我们需要建N棵线段树。最粗暴的想法，对每个新版本都把原版本内容复制一遍，然后修改对应的值。这根本不用想，直接MLE+TLE。那维护历史版本又是怎样实现的呢？

对于本题，每个版本的序列，我们可以建一棵线段树来维护它，所有非叶子节点表示的是一段区间，而叶子节点就表示序列的每一个值了。

举个栗子，样例中初始版本可以长这样——

而版本1只是查询了一下（线段树基本操作，这里不再赘述），然后跟初始版本一模一样。这就没必要复制了嘛！我们设版本i有一个根节点root_i（表示整段区间），根节点有左右儿子，那么我们直接让root_1的左右儿子指向root_0的左右儿子就好了，根本不用复制整个线段树嘛！

那再来看看修改操作。比如从版本1~2。1和0是一样的，而版本2会长这样——

有没有发现1和2真的很像？其实从前到后只改变了一个节点！那么其他相同的地方，我们可不可以共用一段内存呢？

没错，每次创建一个新的版本时，只要新建\log_2 n个节点,也就是只保存从新版本的根节点到更新的那一个叶子节点的路径就可以了，不在此路径上的左/右儿子只要接原版本对应区间的对应儿子就可以啦。我们可以保证，从对应版本的根节点一定能访问到对应叶子节点的值。

下面是加入新版本的具体实现代码(我写的是非递归版）：

#define R register int
inline void insert(R*t,R u,R l,R r,R k)
//t是当前节点指针，u是原版本对应t的节点，l、r为当前区间，k为修改点的位置
{
    R m;
    while(l!=r)
    {
        *t=++P;//为新节点分配空间，P是个外部变量
        m=(l+r)>>1;//线段树操作，计算区间中点
        if(k<=m)r=m,rc[*t]=rc[u],t=&lc[*t],u=lc[u];
        else  l=m+1,lc[*t]=lc[u],t=&rc[*t],u=rc[u];
        //上面两行很关键。（if一行）如果k在左子树中，那么右子树没有变，直接连到旧版本的对应右子树上，t、u更新为当前左子树继续。（else一行反之亦然）
    }
    in(val[*t=++P]);//读入新叶子节点的值
}

整个程序的代码如下

#include<cstdio>
#include<cstring>
#define R register int
const int N=1000009,M=20000009;
int P,rt[N],lc[M],rc[M],val[M];
char I[M<<1],O[M],*fi=I,*fo=O;
bool nega;
inline void in(R&z)
{
    while(*fi<'-')++fi;
    if(*fi=='-')nega=1,++fi;
    z=*fi++&15;
    while(*fi>'-')z*=10,z+=*fi++&15;
    if(nega)nega=0,z=-z;
}
void oi(R z)
{
    if(z>9)oi(z/10);
    *fo++=z%10|'0';
}
inline void out(R z)
{
    z>0?oi(z):(*fo++='-',oi(-z));*fo++='\n';
}//上面快读快写
void build(R&t,R l,R r)//初始化建树，线段树基本操作
{
    R m;
    t=++P;
    if(l!=r)
    {
        m=(l+r)>>1;
        build(lc[t],l,m);
        build(rc[t],m+1,r);
    }
    else in(val[P]);
}
inline void insert(R*t,R u,R l,R r,R k)//更新，插入一个新路径
{
    R m;
    while(l!=r)
    {
        *t=++P;
        m=(l+r)>>1;
        if(k<=m)r=m,rc[*t]=rc[u],t=&lc[*t],u=lc[u];
        else  l=m+1,lc[*t]=lc[u],t=&rc[*t],u=rc[u];
    }
    in(val[*t=++P]);
}
inline int ask(R t,R l,R r,R k)//询问
{
    R m;
    while(l!=r)
    {
        m=(l+r)>>1;
        if(k<=m)r=m,t=lc[t];
        else  l=m+1,t=rc[t];
    }
    return val[t];
}
int main()
{
    fread(I,1,sizeof(I),stdin);
    R n,m,i,v,op,loc;
    in(n);in(m);
    build(rt[0],1,n);
    for(i=1;i<=m;++i)
    {
        in(v);in(op);in(loc);
        if(op&1)insert(&rt[i],rt[v],1,n,loc);
        else
        {
            out(ask(rt[v],1,n,loc));
            rt[i]=++P;//没错，这里的版本复制其实很简单
            lc[P]=lc[rt[v]];
            rc[P]=rc[rt[v]];
        }
    }
    fwrite(O,1,fo-O,stdout);
    fclose(stdin);fclose(stdout);
    return 0;
}