什么是主席树
-
主席树即可持久化线段树
-
这边其实我目前感觉就是支持查询历史版本的线段树
原理
-
每当线段树修改时，维护其过去的版本，将其复制下来（然后就MLE了
-
改进：对集合的每一个版本维护一个单独的根，在修改数据时，只复制树的一部分
-
(复制一张别人的图Orz)
建树
- 类似普通线段树，新建节点
单点更新
- 引用一下别人的博客
我们要修改一个叶子结点的值，并且不能影响旧版本的结构。
在从根结点递归向下寻找目标结点时，将路径上经过的结点都复制一份。
找到目标结点后，我们新建一个新的叶子结点，使它的值为修改后的版本，并将它的地址返回。
对于一个非叶子结点，它至多只有一个子结点会被修改，那么我们对将要被修改的子结点调用修改函数，那么就得到了它修改后的儿子。
在每一步都向上返回当前结点的地址，使父结点能够接收到修改后的子结点。
在这个过程中，只有对新建的结点的操作，没有对旧版本的数据进行修改。
- 其实我这里觉得和建树一样和普通线段树差不太多，只要在原本基础上新建节点就行
区间查询：
- 感觉和普通的区别不大，要查询的版本的根节点开始查就行
代码实现
#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];
}
}
}
咕咕咕好像没学明白