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

· · 题解

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

1. 什么是可持久化线段树

可持久化线段树，某些地方也称主席树。在学习可持久化线段树之前，必须了解线段树基础。如果不会，先学线段树。

从字面意思上理解，这一数据结构类似于把线段树变得持久起来 （我在说废话吗？）。它的一种经典应用就是如本题所示。

对于每一次修改，这个数据结构都可以清晰地记录下来，并且随时访问某一次修改中的某一个数据。

在本题中，就是要求：数组每一次修改之后，都可以访问之前的修改版本并得到某一个数据。

2. 如何实现可持久化线段树

如果每次修改都开一个线段树，很显然，空间复杂度就要乘以 10^5 甚至更大的量级，不切实际。

如何省去不必要的空间呢？不难想到，线段树修改的时候只经过一条链，也就是 \log n 个点，是不是可以只维护每次操作里面的这些点？

是的。这样，空间就只会增加 m \log n 个点了！

具体可以看下面的图。

标红的点是修改所经过的那条链，而橙色的点就是对应过去的黑色点，右侧的黑色点是修改链的新链。

3. 如何编写可持久化线段树

根据上述可持久化线段树的实现，我们可以写出如下代码。

  1. 建一棵初始树（操作 0）

    其实和线段树的建树过程没有太大的区别。

    int build(int p,int pl,int pr){
    p=++tot;
    if(pl==pr){
        tree[p].val=data[pl];
        return p;
    }
    int mid=pl+(pr-pl>>1);
    tree[p].lson=build(0,pl,mid);
    tree[p].rson=build(0,mid+1,pr);
    return p;
}

    注意一下返回的值一定要是整型而不是 void，只有这样才能便于存储左右节点和根节点。

  2. 克隆节点（修改以及克隆节点）

    首先，我们修改的时候会有一条链是修改经过的，所以节点的克隆先直接把节点的数据赋值过去即可。

    inline int clone(int p){
    tree[++tot]=tree[p];
    return tot;
}

    修改操作就是加上克隆操作之后把修改过的节点左儿子或右儿子更新即可。

    int modify(int p,int pl,int pr,int L,int R,ll k){
    p=clone(p);
    if(L<=pl&&pr<=R){
        tree[p].val=k;
        return p;
    }
    int mid=pl+(pr-pl>>1);
    if(L<=mid)tree[p].lson=modify(tree[p].lson,pl,mid,L,R,k);
    if(mid<R)tree[p].rson=modify(tree[p].rson,mid+1,pr,L,R,k);
    return p;
}

  3. 查询

    正常线段树的查询。

    ll query(int p,int pl,int pr,int L,int R){
    if(L<=pl&&pr<=R){
        return tree[p].val;
    }
    int mid=pl+(pr-pl>>1);
    ll ret=0;
    if(L<=mid)ret+=query(tree[p].lson,pl,mid,L,R);
    if(mid<R)ret+=query(tree[p].rson,mid+1,pr,L,R);
    return ret;
}

  4. 主函数

    根据题目要求，先建出操作 0 的树，然后将每次操作，如果是修改，就把第 i 次操作的根节点更新成新建的树的根即可。

    如果是查询，就把第 i 次操作的根节点更新成第 v 次的操作的根节点。

    int main(){
    n=read(),Q=read();
    for(int i=1;i<=n;++i){
        data[i]=read();
    }
    root[0]=build(0,1,n);
    for(int i=1;i<=Q;++i){
        v=read(),opt=read(),p=read();
        if(opt==1){
            c=read();
            root[i]=modify(root[v],1,n,p,p,c);
        }else{
            write(query(root[v],1,n,p,p)),putchar('\n');
            root[i]=root[v];
        }
    }
    return 0;
}

4. 最后注意的小问题

关于数组的大小，由于增加了 m \log n 个节点，保险起见可以开 8 \times 10^7，但这道题可以只用开到 3 \times 10^7 即可。

可持久化线段树封不封装看个人喜好，建议还是封装比较好，毕竟有时候复杂的题目不封装可能看得有点吃力。

创作不易，望管理员大大通过。