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

· · 题解

前置知识：线段树

可持久化数组可以用可持久化线段树或者可持久化平衡树实现，在本篇题解中，因为本蒟蒻只会可持久化线段树， 我们先来研究一下如何使用可持久化线段树实现可持久化数组。

引入

首先，我们对这一题的第一想法是对每一个历史版本新建一个数组别注意题目标题，那不重要。但是，题目庞大的数据范围会使它MLE，那么，我们就需要一种数据结构来优化空间，它就是——可持久化线段树。

原理

可持久化线段树，就是把题目中的数据，放入线段树的叶子节点中操作。等等，放在线段树里？？？这不是更会MLE吗？

本蒟蒻的回答：

其实是不会的。

原理是什么呢？其实，我们对于每一次修改操作，并不用多新建一个线段树，而只用新建一条从根节点到链就可以了。只用新建一条链的原因是因为我们的线段树是以叶子节点储存数据的，我们要以从根节点到这一个叶子节点上所有节点的数据新建出一条链。（如果不理解的话就联系一下线段树的修改操作）（注意：可持久化线段树是新建节点，而不是修改节点数据，因为存储历史版本）

不理解的话可以看一下下图。

可持久化线段树在每一次新建操作只用新建O(logn)个节点，所以它比朴素的算法在空间上要优化多了！

代码

其实这里还有一个关于历史版本的数组rt[]，但非常简单，就不用多说了。

#include<cstdio>
int n,m,rt[1000010],cnt;//cnt记录版本的序号 
struct tree{
    int ls,rs,value;
}t[21000010];
inline void read(int &x,char ch=getchar(),bool f=0)
{
    for(x=0;ch>'9'||ch<'0';f=ch=='-',ch=getchar());
    for(;ch>='0'&&ch<='9';x=(x<<3)+(x<<1)+(ch^48),ch=getchar());
    (f)&&(x=-x);
}
void build(int &point,int l,int r)
{
    point=++cnt;
    if(l==r)
    {
        read(t[point].value);
        return;
    }
    int mid=(l+r)>>1;
    build(t[point].ls,l,mid);
    build(t[point].rs,mid+1,r);
}
void change(int &point,int last,int l,int r,int pos,int value)
{
    point=++cnt,t[point]=t[last];
    if(l==r)
    {
        t[point].value=value;
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid)change(t[point].ls,t[last].ls,l,mid,pos,value);
    else change(t[point].rs,t[last].rs,mid+1,r,pos,value);
}
int que(int point,int l,int r,int loc)
{
    if(l==r)return t[point].value;
    int mid=(l+r)>>1;
    if(loc<=mid)return que(t[point].ls,l,mid,loc);
    else return que(t[point].rs,mid+1,r,loc);
}
int main()
{
    read(n),read(m);
    build(rt[0],1,n);
    for(int i=1,last,flag,x,y,loc;i<=m;i++)
    {
        read(last),read(flag);
        if(flag==1)
        {
            read(x),read(y);
            change(rt[i],rt[last],1,n,x,y);
        }
        else
        {
            read(loc);
            printf("%d\n",que(rt[last],1,n,loc));
            rt[i]=rt[last];//注意新建的版本序号 
        }
    }
}

可持久化数组在可持久化算法中是一个非常重要的知识点，请大家好好记住！

哪一位大佬可以教我可持久化平衡树鸭。。。