【数据结构】可持久化权值线段树（又名主席树）

· · 算法·理论

1. 废话

我从小就有个梦想——学习主席树

2. idea

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

给出一个序列，现在有两种操作：单点修改和单点查询，并且每次操作都会生成一个新版本，我们在进行操作的时候也会给出基于的版本，例如给出序列：2 3 5 4（这是0版），现在查询第2个数（生成1版），再将第1版第3个数改成2，将第2版的第1个数改成5，查询第3版第3个数，将第2版第4个数改成1，最后查询第5版第2个数

用暴力的，每个版本都重新生成数组的方法表达就是这样：

0版 2 3 5 4

1版 2 3 5 4 输出3

2版 2 3 2 4

3版 5 3 2 4

4版 5 3 2 4 输出2

5版 2 3 1 4

6版 2 3 1 4 输出3

显然，这样空间太离谱了，所以我们考虑优化

可以发现，我们每次都是单点修改，所以我们可以只记录修改信息，于是将它拓展为树形结构

3张图涵盖建树、查询、修改

3. 建树

按正常线段树建树方式建树即可

4. 查询

加一个根节点，使之连在复制版本的左右子树上，这样查询时效果与复制没有区别

5. 修改

如果修改下标在左子树的维护范围内，则连右子树，新生成左子树节点。右子树类似，到叶子节点时则直接存修改的数字即可

6. Detail

可以发现，每个版本都会生成一个新的根，则建数组保存各个版本的根，涉及版本时传入对应根节点即可。另外可以发现，每一个根节点都可以分离出来一个完整的线段树

7. 时空复杂度

7.1 空间复杂度

每次加点会多为 \log n 个点（不是左子树就是右子树，所以添加点的数量为树的深度）

m$次操作共 $m\log m$ ，再兼之版$0$的树，一共为 $n+m\log n

7.2 时间复杂度

因为分离的性质，所以为 O(m\log n)

8. 代码

都讲到这里了，我认为已经可以对着图打出来了，但还是放一下吧……

#include <iostream>
#include <cstdio>
using namespace std;
struct node
{
    int dat,ls,rs;
}tr[40000005];
int n,m,a[2000005],ttop,task,x,y,z,root[2000005],version;
int makenode(int dat=0)
{
    ttop++;
    tr[ttop].dat=dat;
    return ttop;
}
int build(int l,int r)
{
    int now=makenode();
    if(l==r)
    {
        tr[now].dat=a[l];
        return now;
    }
    int mid=(l+r)>>1;
    tr[now].ls=build(l,mid);
    tr[now].rs=build(mid+1,r);
    return now;
}
int change(node copy,int l,int r,int p,int k)
{
    int now=makenode();
    if(l==r)
    {
        tr[now].dat=k;
        return now;
    }
    int mid=(l+r)>>1;
    if(p<=mid)
    {
        tr[now].ls=change(tr[copy.ls],l,mid,p,k);
        tr[now].rs=copy.rs;
    }
    if(mid+1<=p)
    {
        tr[now].ls=copy.ls;
        tr[now].rs=change(tr[copy.rs],mid+1,r,p,k);
    }
    return now;
}
int query(int now,int l,int r,int p)
{
    if(l==r) return tr[now].dat;
    int mid=(l+r)>>1;
    if(p<=mid) return query(tr[now].ls,l,mid,p);
    else return query(tr[now].rs,mid+1,r,p);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    root[0]=build(1,n);
    while(m--)
    {
        scanf("%d%d%d",&x,&task,&y);
        if(task-1)
        {
            root[++version]=makenode();
            tr[root[version]]=tr[root[x]];
            cout<<query(root[x],1,n,y)<<'\n';
        }
        else
        {
            scanf("%d",&z);
            root[++version]=change(tr[root[x]],1,n,y,z);
        }
    }
    return 0;
}

注意常数优化QAQ