主席树初步

什么是主席树

• 主席树即可持久化线段树

• 这边其实我目前感觉就是支持查询历史版本的线段树

原理

• 每当线段树修改时，维护其过去的版本，将其复制下来（然后就MLE了

• 改进：对集合的每一个版本维护一个单独的根，在修改数据时，只复制树的一部分

• (复制一张别人的图Orz)

建树

• 类似普通线段树，新建节点

单点更新

• 引用一下别人的博客

我们要修改一个叶子结点的值，并且不能影响旧版本的结构。
在从根结点递归向下寻找目标结点时，将路径上经过的结点都复制一份。
找到目标结点后，我们新建一个新的叶子结点，使它的值为修改后的版本，并将它的地址返回。
对于一个非叶子结点，它至多只有一个子结点会被修改，那么我们对将要被修改的子结点调用修改函数，那么就得到了它修改后的儿子。
在每一步都向上返回当前结点的地址，使父结点能够接收到修改后的子结点。
在这个过程中，只有对新建的结点的操作，没有对旧版本的数据进行修改。

• 其实我这里觉得和建树一样和普通线段树差不太多，只要在原本基础上新建节点就行

区间查询：

• 感觉和普通的区别不大，要查询的版本的根节点开始查就行

代码实现

• 你谷P3919

#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL a[0x66ccff*5],n,q,rt[0x66ccff*5];
inline LL read(){
    LL f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
LL lc[0x66ccff*5],rc[0x66ccff*5],val[0x66ccff*5],ans,m,v;
inline void build(LL &q,LL l,LL r){
    q=++ans;
    if(l==r){
        val[q]=a[l];
        return;
    }
    LL mid=(l+r)>>1;
    build(lc[q],l,mid);
    build(rc[q],mid+1,r);
}
inline void change(LL &m,LL tot,LL l,LL r,LL q,LL v){
    m=++ans;//新建节点
    lc[m]=lc[tot];
    rc[m]=rc[tot];
    val[m]=val[tot];
    if(l==r){
        val[m]=v;
        return;
    }
    LL mid=(l+r)>>1;
    if(q<=mid)
        change(lc[m],lc[tot],l,mid,q,v);
    else 
        change(rc[m],rc[tot],mid+1,r,q,v);
}
inline LL ask(LL m,LL l,LL r,LL q){
    if(l==r)
        return val[m];
    else{
        LL mid=(l+r)>>1;
        if(q<=mid)
            return ask(lc[m],l,mid,q);
        else 
            return ask(rc[m],mid+1,r,q);
    }
}
int main(){
    n=read(),m=read();
    for(LL i=1;i<=n;i++)
        a[i]=read();
    build(rt[0],1,n);
    for(LL i=1;i<=m;i++){
        LL tot=read(),opt=read(),x=read();
        if(opt==1)
			v=read();
			change(rt[i],rt[tot],1,n,x,v);
        if(opt==2){
			cout<<ask(rt[tot],1,n,x)<<"\n";
			rt[i]=rt[tot];
		}
    }
}

咕咕咕好像没学明白