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

一、题目描述：

　　维护这样的一个长度为 $n$ 的数组，支持以下两种操作

　　　　$1$：在某个历史版本上修改某一个位置上的值

　　　　$2$：访问某个历史版本上的某一位置的值

　　每进行一次操作，就会生成一个新的版本（对于操作2，生成的就是一个完全一样的版本）。

　　版本编号即为当前操作的编号（从 $1$ 开始编号，版本 $0$ 表示初始状态数组）。共有 $m$ 次询问。

　　数据范围：$1 \leq n，m \leq 10^6$ 。

 二、解题思路：

　　板子题，不需要思路。主席树，时空复杂度均为 $O(nlogn)$ 。

 三、完整代码：

 1 #include<iostream>
 2 #define N 1000010
 3 using namespace std;
 4 int n,m,k,x,y,opt,tot;
 5 int a[N],rt[N];
 6 struct ST{
 7     int ls,rs,val;
 8 }t[N*80];
 9 void build(int &p,int l,int r)
10 {
11     if(!p)    p=++tot;
12     if(l==r)
13     {
14         t[p].val=a[l];
15         return ;
16     }
17     int mid=(l+r)>>1;
18     build(t[p].ls,l,mid);
19     build(t[p].rs,mid+1,r);
20 }
21 void update(int &p1,int p2,int l,int r,int pos,int val)
22 {
23     if(!p1)    p1=++tot;
24     if(l==r)
25     {
26         t[p1].val=val;
27         return ;
28     }
29     int mid=(l+r)>>1;
30     if(pos<=mid)
31     {
32         t[p1].rs=t[p2].rs;
33         update(t[p1].ls,t[p2].ls,l,mid,pos,val);
34     }
35     else
36     {
37         t[p1].ls=t[p2].ls;
38         update(t[p1].rs,t[p2].rs,mid+1,r,pos,val);
39     }
40 }
41 int query(int p,int l,int r,int pos)
42 {
43     if(l==r)  return t[p].val; int mid=(l+r)>>1;
44     if(pos<=mid)return query(t[p].ls,l,mid,pos);
45     else        return query(t[p].rs,mid+1,r,pos);
46 }
47 int main()
48 {
49     ios::sync_with_stdio(false);
50     cin.tie(0);cout.tie(0);
51     cin>>n>>m;
52     for(int i=1;i<=n;i++)
53         cin>>a[i];
54     build(rt[0],1,n);
55     for(int i=1;i<=m;i++)
56     {
57         cin>>k>>opt;
58         if(opt==1)
59         {
60             cin>>x>>y;
61             update(rt[i],rt[k],1,n,x,y);
62         }
63         if(opt==2)
64         {
65             cin>>x;rt[i]=rt[k];
66             cout<<query(rt[i],1,n,x)<<'\n';
67         }
68     }
69     return 0;
70 }

 四、写题心得：

　　根本就很简单嘛！之前以为主席树是特别玄学的东西，结果今天一遍就过了。有一点线段树合并的感觉。加油，拜拜！