注：学习可持久化线段树之前一定要先完全明白线段树的逻辑和原理还有线段树动态开点的方法，如果有不是特别理解可以阅读我之前的文章，有详细的线段树原理图解和解析。链接：【数据结构进阶】万字图解线段树：从前缀和到区间修改的完美进化 (洛谷P3372 附C++模板)-CSDN博客

线段树动态开点：【数据结构进阶】拒绝4倍空间！图解动态开点线段树：如何解决空间爆炸？(洛谷p13825 含C++模板)-CSDN博客

洛谷 P3919 链接：P3919 【模板】可持久化线段树 1（可持久化数组） - 洛谷

此前利用线段树，我们就能很好的处理比较大的数据（ $10^5$ 或者 $10^6$ ）下的对数组里的值进行区间的修改或者查询。但是现在我们又增加了一个要求：每次修改或者查询，我们都要以此作为一个新版本保存下来，而且此后还要可以随时再访问回去那个版本进行修改或者查询。

最直接的办法，我们可以每次修改和查询，都重新复制保存上一个版本的一整个线段树吗？这显然就不行了。即使是 $10^5$ 的数据量，我们每一颗线段树都几乎要耗掉 4×$10^5$ 的大小节点，更别说我们的操作次数可能高达 $10^5$ 次，那就要耗掉 4×$10^{10}$ 大小的节点了。这几乎必然 MLE 。所以，我们需要想一个更好的办法去为了保存更多的版本而节省内存才行。

我们可以发现，有时候我们的修改，可能仅仅涉及某一个小区间，而其他地方都是没有变化的，而我们却粗暴地将整个线段树复制为一个新版本。比如我维护总区间 [1,10] 的数据，我修改的区间仅仅涉及小区间 [7,9] ，而其他区间 [1,6] 和 [10,10] 都是未经修改的，和旧版本完全一样。那我们完全可以在建这个新版本的时候，只单独修改区间 [7,9] ，而其他区间 [1,6] 和 [10,10] 完全可以直接通过指针指向上一个版本直接复用无需复制了。实际上每次只会新建从根到被修改位置的那条路径上的节点，其数量为 O(logN)，其余子树结构完全复用旧版本，这样就可以大大节省了内存。

所以到了这里，我们就可以得知这个可持续化线段树的思想：每次建立新版本的时候，只开出和旧版本不同的节点进行保存，而和旧版本完全一样的节点区间我们直接利用指针直接复用旧版本的数据，减少了重复数据的多次重复保存。

这其实也和我们常用的 git 工具有异曲同工之妙。我们用 git 来进行版本控制的时候，也可以发现 git 并不是傻傻地完全复制我们一整个代码文件保存，而是仅仅提交我们对某些文件的修改，而其他我们没动过的文件 git 也是只保存修改内容，其余内容直接复用已有版本。

实现思路

初始变量和数组

这个 P3919 的模板题的修改操作比较简单，是单点修改；而且查询操作也是查单点值。所以这道题也就暂时不需要用到线段树懒标记了，只需要在叶子节点存储我们的值，然后利用线段树的修改和查询方法即可。但如果以后碰到比如要维护前缀和或者其他的区间操作，可以自己尝试加上节点的懒标记，目前主要是理解可持久化的实现方法。

由于我们是要看当前修改情况来新开线段树节点，所以我们必须采用动态开点的方法来构建不同版本线段树。可以用一个 cnt 变量来分配每个节点的编号。

其次，我们也要快速找到我们想要的版本位置，所以我们需要开一个数组 rt 来记录不同版本线段树的根节点，这样我们才能任意进入对应版本的线段树了。即 rt[i] 是第 i 个版本的线段树的根节点编号。

还要两个数组 ls 和 rs 记录每个节点的左子节点和右子节点的编号，才能支持我们在线段树上递归地修改和查询。即 ls[i] 代表节点编号为 i 的左子节点的编号，rs[i] 代表节点编号为 i 的右子节点的编号。

最后，还需要一个 val 数组来记录编号为 i 的节点对应的值，方便查询或者修改得到我们想要的值。即 val[i] 代表节点编号为 i 的叶子节点对应的值。要注意的是本题由于只做单点修改和单点查询，因此内部节点无需维护区间信息，只需保持左右子节点的树形结构而已，所以 val 其实只有叶子节点是的值是这题需要的，其他都是没用的。

每一次我们建立新版本的线段树的时候，实质是要新建立一条从根节点到叶子节点的路径，空间复杂度为 O(logN) 。而在这道题我们可以分析出我们要有起码 m 个版本的线段树，还有最原始的 O(n) 的静态线段树，算下来空间复杂度应该是 O(MlogN+N) 。如果是 $10^6$ 的数据量，($10^6$) ≈ 20，预估节点总数是 n+m×20 ，我们开数组 $10^6$×40 就足够了。

const int maxn=1e6+5;
int rt[maxn];//记录每一个版本线段树的根节点编号
int ls[maxn*40];//记录每个节点的左子节点编号
int rs[maxn*40];//记录每个节点的右子节点编号
int val[maxn*40];//存储编号为i的叶子节点对应的值
int arr[maxn];//存储初始的数组值
int cnt;//动态开点用于分配节点编号

这里我就没有使用结构体来建立线段树而是用数组。如果用结构体同样也是可行的，并无什么差别。

const int maxn=1e6+5;
int rt[maxn];//记录每一个版本线段树的根节点编号
struct node{
    int ls,rs;
    int val;
}tr[maxn*40];//ls左子节点，rs右子节点，val是节点的值
int arr[maxn];//存储初始的数组值
int cnt;//动态开点用于分配节点编号

build 最初始版本

我们首先肯定是要建立初始的版本的完整的静态线段树，也就是对题目给出的数组 arr 建立一个线段树。这样才能在此基础上延伸出不同版本的线段树。我们可以直接在 rt[0] 放我们这个线段树的根节点编号，作为最初始版本的线段树，即第 0 个版本。

我们利用 cnt 给不同的节点分配一个专属编号，并最好直接 build 可以直接返回节点编号方便赋值。其余写法和我们普通线段树其实没什么差别。

//l是区间左边界，r是区间右边界
int build(int l,int r){
    int p=++cnt;//分配编号，当前节点编号为p
    //到达叶子节点，直接赋值并返回节点编号
    if(l>=r){
        val[p]=arr[l];
        return p;
    }
    int mid=(l+r)>>1;
    //递归调用build
    ls[p]=build(l,mid);//给左子节点编号赋值
    rs[p]=build(mid+1,r);//给右子节点编号赋值
    //处理好当前这个节点的左右子节点就可以返回编号p了
    return p;
}

在主函数里调用方法即

rt[0]=build(1,n);

以题目数据为例，我们执行完 build 函数后，就能得到以下的初始线段树了。

update 修改（重！！！）

接下来我们就要考虑这个 update 函数的代码实现了。按照我们刚刚的想法，我们主要要做的，就是对该复用的地方进行复用，而对需要修改的地方开出新的节点进行修改。

下面先给出 update 函数的代码及详细注释，对应的代码进行解释应该能更清晰地理解。

//l和r是区间左右边界，p是我们要修改的位置，c是要改的值，pre是我们要的旧版本对应此时新版本节点位置的编号
int update(int l,int r,int p,int pre,int c){
    int t=++cnt;//对当前节点分配一个编号t
    //先进行复用，当前节点t对应旧版本的节点pre，对旧版本的左右节点都进行复用
    ls[t]=ls[pre];
    rs[t]=rs[pre];
    //到达叶子节点，同时也到了需要修改的那个位置了，直接赋值修改
    if(l>=r){
        val[t]=c;
        return t;
    }
    int mid=(l+r)>>1;
    //p是数组要修改的位置，p比mid小说明要修改的位置在左子节点的区间，从而应该直接进入左子节点修改，右子节点不需要修改则直接复用；p比mid大同理
    if(p<=mid) ls[t]=update(l,mid,p,ls[pre],c);
    else rs[t]=update(mid+1,r,p,rs[pre],c);
    //修改完成return节点编号
    return t;
}

我们首先必须理解 pre 参数的意义。如当前新版本线段树节点编号是 t ，而这个节点 t 在新版本线段树所在的位置对应旧版本线段树所处的位置，就是节点编号为 pre 的节点。我们可以直接模拟一次建立新版本树的过程来理解一下。我会用蓝线代表新版本树的指针指向链接。

假设我要将数组索引为 3 （参数p）的位置修改成 66 （参数c）。首先是给 rt[1] 版本打上新编号，当前情况下，它的 pre 应该是上一次版本的根节点 rt[0] 。

对应的旧版本的左右节点我们直接复用。但我们运行发现，修改的 p 位置属于左子节点区间，所以我们继续 update 递归调用在左子节点区间，即左子节点不再复用旧版本，而是新建节点。这个时候注意观察代码里的 pre 传参，我们的 pre 也变成了对应了旧版本节点。

同理，继续进行对旧版本左右子节点的复用。发现我们的要修改的位置 p 在右子节点，所以继续对右子节点进行 update 调用，而左子节点保持复用旧版本。

此时发现已经到了叶子节点了，直接赋值修改即可。

这就是一次完整的修改 update 调用了。我们顺着蓝线和和旧版本的黑线往下走，能发现我们的 rt[1] 版本线段树是一点没遗漏地存下来的。而在这次例子里我们仅仅只开了 3 个节点，就成功储存好了这个新版本 rt[1] 的线段树了。这比我们直接全部复制要用到 9 个节点节省非常多，在数据量大的时候节省内存更为明显，因为要开多少节点其实取决于树的高度，即 O(logN)。

query 查询

其实难点主要在 update 函数而已，query 查询函数难度不大。利用 ls 和 rs 数组存储的左右子节点，加上到达叶子节点 return 即可。在 main 函数中，按题目的意思连查询也需要新建版本，而查询并没有发生修改，直接完全复用旧版本即可。下面是对应的代码及注释。

//l和r是区间左右边界,v是当前节点编号而第一次调用的时候就是版本编号，p是查询的数组索引位置
int query(int l,int r,int v,int p){
    if(l>=r) return val[v];//到达叶子节点return
    int mid=(l+r)>>1;
    if(p<=mid) return query(l,mid,ls[v],p);//在左子节点就递归查询
    return query(mid+1,r,rs[v],p);//右子节点同理
}

总结

理解完全部的代码之后，其实这也并不算特别难。最重要的，是理解可持久化的这个算法思想。面对需要多个版本保存的时候，对相同的地方完全可以进行复用而不是多次复制导致冗余，只对两个版本不同的地方进行独立的修改和存储。这种思想不仅仅可以用于线段树，还可以用于其他数据结构进行结合，比如权值线段树，并查集等等，实现多种用途。

最后给出这道题目的完整代码。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int rt[maxn];//记录每一个版本线段树的根节点编号
int ls[maxn*40];//记录每个节点的左子节点编号
int rs[maxn*40];//记录每个节点的右子节点编号
int val[maxn*40];//存储编号为i的叶子节点对应的值
int arr[maxn];//存储初始的数组值
int cnt;//动态开点用于分配节点编号
//l和r是区间左右边界
int build(int l,int r){
    int p=++cnt;//分配编号，当前节点编号为p
    //到达叶子节点，直接赋值并返回节点编号
    if(l>=r){
        val[p]=arr[l];
        return p;
    }
    int mid=(l+r)>>1;
    //递归调用build
    ls[p]=build(l,mid);//给左子节点编号赋值
    rs[p]=build(mid+1,r);//给右子节点编号赋值
    //处理好当前这个节点的左右子节点就可以返回编号p了
    return p;
}
//l和r是区间左右边界，p是我们要修改的位置，c是要改的值，pre是我们要的旧版本对应此时新版本节点位置的编号
int update(int l,int r,int p,int pre,int c){
    int t=++cnt;//对当前节点分配一个编号t
    //先进行复用，当前节点t对应旧版本的节点pre，对旧版本的左右节点都进行复用
    ls[t]=ls[pre];
    rs[t]=rs[pre];
    //到达叶子节点，同时也到了需要修改的那个位置了，直接赋值修改
    if(l>=r){
        val[t]=c;
        return t;
    }
    int mid=(l+r)>>1;
    //p是数组要修改的位置，p比mid小说明要修改的位置在左子节点的区间，从而应该直接进入左子节点修改，右子节点不需要修改则直接复用；p比mid大同理
    if(p<=mid) ls[t]=update(l,mid,p,ls[pre],c);
    else rs[t]=update(mid+1,r,p,rs[pre],c);
    //修改完成return节点编号
    return t;
}
//l和r是区间左右边界,v是当前节点编号而第一次调用的时候就是版本编号，p是查询的数组索引位置
int query(int l,int r,int v,int p){
    if(l>=r) return val[v];//到达叶子节点return
    int mid=(l+r)>>1;
    if(p<=mid) return query(l,mid,ls[v],p);//在左子节点就递归查询
    return query(mid+1,r,rs[v],p);//右子节点同理
}
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>arr[i];
    rt[0]=build(1,n);//首先build初始rt[0]版本
    for(int i=1;i<=m;++i){
        int v,op,p;//v是版本号，op是操作类型，p是要操作的数组索引位置
        cin>>v>>op>>p;
        if(op==1){
            int c;
            cin>>c;
            rt[i]=update(1,n,p,rt[v],c);
        }else{
            cout<<query(1,n,rt[v],p)<<'\n';
            rt[i]=rt[v];
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T=1;
    //cin>>T;
    while(T--){
        solve();
    }
}