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

· · 题解

可持久化数组，可以访问历史版本的数组。

我们考虑使用可持久化数据结构——主席树，如果不理解可以左转模板。

主席树对数组的每一个前缀建树。我们都知道其中root数组表示前缀1..i主席树的根。 那我们现在换一种方式建树，我们对每一次操作带来的版本建线段树，维护数组的权值。

什么意思呢？看图(我们设这个数组为a={1,2,3,4})：

我们发现，这棵线段树叶子节点的权值就是它所对应数组内数的权值，这和普通线段树是类似的。

但是我们令非叶子节点的权值为空。这只是为了方便二分查找而设置的。

所以我们在查询数组内数的值时，直接单点询问就可以了，时间复杂度O(logN)

int query(int rt,int l,int r,int kkk){
    if (l==r) return tree[rt].sum;
    int mid=(l+r)>>1;
    if (kkk<=mid) return query(tree[rt].l,l,mid,kkk);
    else return query(tree[rt].r,mid+1,r,kkk);
}
主程序内：
query(树根,1,n,访问数组的下标);

我们令初始状态为第0个状态，这个树根即为root[0]。 如果我们把a[4]改为5呢？我们新建一个根root[1]

和主席树一样，数组a[1]、a[2]没有变化，直接连接，和主席树一样。

创造右节点。

然后a[3]也没有变化，连接

随后，创造新的叶子节点(a[4]=5)

代码和主席树神似。

void build(int &rt,int l,int r){
    rt=++cnt;
    if(l==r){tree[rt].sum=a[l];return;}
    int mid=(l+r)>>1;
    build(tree[rt].l,l,mid);build(tree[rt].r,mid+1,r);
}//初始建设
void update(int num,int &rt,int l,int r){
    tree[++cnt]=tree[rt]; rt=cnt; 
    int mid=(l+r)/2;
    if (l==r){tree[rt].sum=aaaa; return;}
    if (num<=mid) update(num,tree[rt].l,l,mid);
    else update(num,tree[rt].r,mid+1,r);
}//更新

时间复杂度O(logN)，我们发现，这次修改我们创造了一个新树根(root[1]),这恰好表示了第一次修改后的状态。

这么一来，回到某一个状态，就很简单了，若要访问某一个状态i，访问或更新时直接使用root[i]即可。

代码如下：

#include<bits/stdc++.h>
#define res register int 
#define ll long long
#define jsz inline
using namespace std;
int cnt,n,a[1000660],m,root[1000660],aaaa;
jsz int read(){
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){
        if (ch=='-')f=-1;
        ch=getchar();
    }
    while (isdigit(ch)){
        x=x*10+ch-48;
        ch=getchar();
    }
    return x*f;
}
struct ZXT{
    int l,r,sum;
}tree[20006660];
jsz void build(int &rt,int l,int r){
    rt=++cnt;
    if(l==r){tree[rt].sum=a[l];return;}
    int mid=(l+r)>>1;
    build(tree[rt].l,l,mid);build(tree[rt].r,mid+1,r);
}
jsz void update(int num,int &rt,int l,int r){
    tree[++cnt]=tree[rt]; rt=cnt; 
    int mid=(l+r)/2;
    if (l==r){tree[rt].sum=aaaa; return;}
    if (num<=mid) update(num,tree[rt].l,l,mid);
    else update(num,tree[rt].r,mid+1,r);
}
jsz int query(int rt,int l,int r,int kkk){
    if (l==r) return tree[rt].sum;
    int mid=(l+r)>>1;
    if (kkk<=mid) return query(tree[rt].l,l,mid,kkk);
    else return query(tree[rt].r,mid+1,r,kkk);
}
int main(){
    n=read();m=read();
    for (res i=1;i<=n;i++) a[i]=read();
    build(root[0],1,n);
    for (res i=1;i<=m;i++){
        int xxxx=read();int yyyy=read();
        if (yyyy==1){
            int zzzz=read();aaaa=read();
            root[i]=root[xxxx];
            update(zzzz,root[i],1,n);
        }else{
            int zzzz=read();
            printf("%d\n",query(root[xxxx],1,n,zzzz));
            root[i]=root[xxxx];
        }
    }
}