以为例。

 

 

知识点：1.练习可持久化线段树

　　　　2.线段树维护数列。线段树维护数列单点查询仅需O(logn)

　　　　3.记得return root;

　　　　4.记得设置左右儿子

　　　　5.有时需注意cnt的初始大小

#include 
     
      using namespace std;int n,m;int rt[2000002];int ls[2000002 * 20],rs[2000002 * 20];int cnt;int tre[2000002 * 20];int build(int l,int r){    int root = ++cnt;    if(l == r)    {        scanf("%d",&tre[root]);        return root;    }    int mid = (l + r) / 2;    ls[root] = build(l,mid);    rs[root] = build(mid + 1,r);    return root;}int query(int t,int l,int r,int b){    if(l == r)return tre[t];    int mid = (l + r) >> 1;    if(b <= mid )return query(ls[t],l,mid,b);    else return query(rs[t],mid + 1,r,b);}int updata(int t,int l,int r,int b,int k){    int root = ++cnt;    if(l == r)    {        tre[root] = k;        return root;    }    //错误1：忘记为新建节点root设置左右儿子，    //漏了 ls[root] = ls[t];    rs[root] = rs[t];    //if(b <= mid)后面漏了ls[root] =     //else 后面漏了rs[root] =      ls[root] = ls[t];    rs[root] = rs[t];    int mid = (l + r) / 2;    if(b <= mid)ls[root] = updata(ls[t],l,mid,b,k);    else rs[root] = updata(rs[t],mid + 1,r,b,k);    return root;}int main(){    scanf("%d%d",&n,&m);    rt[0] = build(1,n);    int x,y,z,a;    for(int i = 1;i <= m;i++)    {        scanf("%d%d%d",&x,&y,&z);        if(y == 2)        {            rt[i] = rt[x];            printf("%d\n",query(rt[x],1,n,z));        }        else if(y == 1)        {            scanf("%d",&a);            rt[i] = updata(rt[x],1,n,z,a);        }    }    return 0;}