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

学习博客：http://www.cnblogs.com/flashhu/p/8297581.html

题目链接：https://www.luogu.org/problemnew/show/P3919

很裸的可持久化线段树板子题。可持久嘛！就是当出现历史版本的时候，能够非常方便地维护一个区间的历史版本。
自然，我们需要建log2⁡n个节点,也就是只保存从新版本的根节点到更新的那一个叶子节点的路径就可以了，不在此路径上的左/右儿子只要接原版本对应区间的对应儿子就可以啦。我们可以保证，从对应版本的根节点一定能访问到对应叶子节点的值。

看代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
const LL INF=1e9+7;
const int maxn=1e6+50;
int N,M;
int tot=0;
int a[maxn];//输入数组
int root[maxn<<5];//root[i]表示版本号问i的线段树的根节点编号  数组开大点

struct Node
{
    int lc,rc,v;
}t[maxn<<5];//数组开大点

int Build(int l,int r)
{
    int pos=++tot;
    if(l==r)
    {
        t[pos].v=a[l];
        return pos;
    }
    int mid=(l+r)>>1;
    t[pos].lc=Build(l,mid);
    t[pos].rc=Build(mid+1,r);
    return pos;
}
int Update(int old,int tar,int c,int l,int r)//老版本 修改a[tar]为c
{
    int pos=++tot;
    if(l==r)
    {
        t[pos].v=c;
        return pos;
    }
    t[pos].lc=t[old].lc;
    t[pos].rc=t[old].rc;//复制老树

    int mid=(l+r)>>1;
    if(tar<=mid) t[pos].lc=Update(t[old].lc,tar,c,l,mid);
    else t[pos].rc=Update(t[old].rc,tar,c,mid+1,r);
    return pos;
}
int query(int pos,int p,int l,int r)
{
    if(l==r)
    {
        return t[pos].v;
    }
    int mid=(l+r)>>1;
    if(p<=mid) return query(t[pos].lc,p,l,mid);
    else return query(t[pos].rc,p,mid+1,r);
}
int main()
{
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++) scanf("%d",&a[i]);
    root[0]=Build(1,N);
    int v,x,l,w;
    for(int i=1;i<=M;i++)
    {
        scanf("%d%d%d",&v,&x,&l);
        if(x==1)
        {
            scanf("%d",&w);
            root[i]=Update(root[v],l,w,1,N);
        }
        else
        {
            root[i]=root[v];//直接复制就行  因为都一样
            printf("%d
",query(root[v],l,1,N));
        }
    }
    return 0;
}

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

相关推荐