可持久化數組再了解

吐槽：

今天是集訓的最後一天，也不知道該學什麼，就再複習一下可持久化的思想，又鞭屍了一遍可持久化數組。

可持久化思想：

對于每次修改的數組我們建立一個新版本，因為我們是動态開點式，對于可以利用的點進行利用，是以空間方面會節省很大。我們将上一版本的樹複制一遍，将沒有利用到的點省去重新開這個點所多出的空間，用圖表示也就是将新開的一條鍊連上上一個沒有用到的點，形成的一顆新樹

對于多版本​

​root[]​

​數組的了解

對于剛剛學習可持久化主席樹，或者可持久化數組，我們都會見到一個​

​root[ ]​

​​，像我一樣的菜雞一定很困惑為什麼這樣就能新開一個新的版本，因為​

​root[ ]​

​數組儲存的是每一個版本的根節點，我們通過根節點向左向右查詢就能找到某一版本的值，因為從根建立，從根查詢是一樣的原理，由于建立出來了，是以查詢根據同樣原理查詢即可

#include<bits/stdc++.h>
using namespace std;
//可持久化并查集
const int maxn =1e6+5;
int n,m,cnt;
struct node
{
    int l,r,val;
} tr[maxn*40];
int a[maxn];
int root[maxn];
void build(int &now,int l,int r)//建第一個版本的數組
{
    now=++cnt;
    if(l==r)
    {
        tr[now].val=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(tr[now].l,l,mid);
    build(tr[now].r,mid+1,r);
}
void modify(int ver,int &now,int l,int r,int pos,int w)//修改版本
{
    now=++cnt;
    tr[now]=tr[ver];
    if(l==r)
    {
        tr[now].val=w;
        return ;
    }
    int mid=l+r>>1;
    if(mid>=pos)
    {
        modify(tr[ver].l,tr[now].l,l,mid,pos,w);
    }
    else
    {
        modify(tr[ver].r,tr[now].r,mid+1,r,pos,w);
    }
}
int query(int ver,int l,int r,int pos)
{
    if(l==r)
    {
        return tr[ver].val;

    }
    int mid=l+r>>1;
    if(mid>=pos)
    {
        return query(tr[ver].l,l,mid,pos);
    }
    else
    {
        return query(tr[ver].r,mid+1,r,pos);
    }

}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    build(root[0],1,n);
    for(int i=1; i<=m; i++)
    {
        int ver,op,pos,w;
        scanf("%d %d",&ver,&op);
        if(op==1)
        {
            scanf("%d %d",&pos,&w);
            modify(root[ver],root[i],1,n,pos,w);
        }
        if(op==2)
        {
            scanf("%d",&pos);
            printf("%d\n",query(root[ver],1,n,pos));
            root[i]=root[ver];
        }
    }
}