可持久化线段树入门小结
以前学过可持久化线段树，但是只会做区间第k小qwq(逃)。决定这段时间重新捡回来。
推荐博客 https://www.cnblogs.com/flashhu/p/8301774.html
https://yjzoier.gitee.io/hexo/p/af72.html
首先是可持久化线段树
可持久化线段树即可以访问历史版本的线段树，暴力做法我们可以对每个历史版本建一棵线段树，容易发现这样会MLE。因为连续版本只是插入一个数的关系，我们发现其实版本i和版本i-1只有一条链的差别（从根节点到插入数的叶子结点这条链），所有我们可以让版本i和版本i-1公用相同结点而只建立新的不同链。
这样的可持久化线段树插入和查询时间依然是O(logn)，且这N棵线段树的空间只要NlogN。
但是要注意的是因为结点公用的关系，其实我们不能修改历史版本的信息，而只能发布新版本。
以洛谷P3919为模板
#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int n,m,a[N],root[N]; int cnt=0,lc[N<<6],rc[N<<6],val[N<<6]; //动态建树函数 一般都会返回新建结点编号 int build(int l,int r) { int q=++cnt; //动态建树 if (l==r) { lc[q]=rc[q]=0; val[q]=a[l]; return q; } int mid=l+r>>1; lc[q]=build(l,mid); rc[q]=build(mid+1,r); return q; } //这个其实是插入函数，因为公用结点的缘故并不能修改版本信息导致其他版本受影响 int update(int p,int l,int r,int x,int v) { //新版本线段树是基于版本p而来 int q=++cnt; //动态建树 if (l==r) { lc[q]=rc[q]=0; val[q]=v; return q; } int mid=l+r>>1; lc[q]=lc[p]; rc[q]=rc[p]; val[q]=val[p]; //为了公用信息，先复制一份 if (x<=mid) lc[q]=update(lc[p],l,mid,x,v); if (x>mid) rc[q]=update(rc[p],mid+1,r,x,v); return q; } int query(int p,int l,int r,int x) { //查询版本p位置x的值 if (l==r) return val[p]; int mid=l+r>>1; if (x<=mid) return query(lc[p],l,mid,x); if (x>mid) return query(rc[p],mid+1,r,x); } int main() { cin>>n>>m; for (int i=1;i<=n;i++) scanf("%d",&a[i]); root[0]=build(1,n); for (int i=1;i<=m;i++) { int k,opt,x,v; scanf("%d%d",&k,&opt); if (opt==1) { scanf("%d%d",&x,&v); root[i]=update(root[k],1,n,x,v); } else { scanf("%d",&x); printf("%d ",query(root[k],1,n,x)); root[i]=root[k]; } } return 0; }
然后我们接着讲主席树，主席树和可持久化线段树到底是什么关系我也不太明白(知乎上有人说是包含关系,有人说是同一样东西)，没所谓反正这又不是重点（逃）。不管怎样主席树和可持久化线段树确实结构上很像，但是主席树的思想要更为复杂一些。这里说一下本蒟蒻的理解，如果错了还请各位大佬指出，蒟蒻感激不尽 。
先是静态的主席树，我们以洛谷P3834为例。
首先给出一句话：可持久化线段树+权值线段树+前缀和思想=主席树
这怎么理解呢？我们先考虑一种暴力的做法：对于前1个数建第一棵权值线段树（当然你得先去了解什么是权值线段树不然没法往下看），对于前2个数建第二棵权值线段树，对于前3个数建第三棵权值线段树......对于前n个数建第n棵权值线段树。然后我们开始处理询问，例如询问为区间[ql,qr]中第K小的数是那个？那么我们看第ql-1棵权值线段树和第qr棵权值线段树，假设在第ql-1棵线段树结点p代表[l,r]区间而在第qr棵线段树结点q代表[l,r]区间，仔细观察因为我们上诉建权值线段树的时候是用了一种前缀和思想建立的，那么此时的sum[lson[q]]-sum[lson[p]]是不是就代表权值位于[l,mid] (mid=l+r>>1) 的数的个数（并且这些数一定是询问中[ql,qr]区间中的数：这是前缀和相减的缘故）。那么我们不断左右细分最终就能得到答案。
上诉算法在时间上询问是logn的，但问题是建立n棵权值线段树会MLE。回想起我们先讲的可持久化线段树，我们发现：哎，这n棵权值线段树不就可以公用结点信息变成可持久化线段树吗？于是我们共用一下信息，呼呼呼，终于得到主席树啦。
#include<bits/stdc++.h> using namespace std; const int N=2e5+10; int n,q,tot,cnt=0; int a[N],b[N],root[N]; struct node{ int lc,rc,sum; }tree[N<<5]; void pushup(int x) { tree[x].sum=tree[tree[x].lc].sum+tree[tree[x].rc].sum; } int Build(int l,int r) { //初始版本的树，动态建树 int q=++cnt; if (l==r) { tree[q].sum=0; tree[q].lc=tree[q].rc=0; return q; } int mid=l+r>>1; tree[q].lc=Build(l,mid); tree[q].rc=Build(mid+1,r); return q; } int Insert(int p,int l,int r,int val) { //增加新点并返回编号 int q=++cnt; if (l==r) { tree[q].lc=tree[q].rc=0; tree[q].sum=tree[p].sum+1; return q; } int mid=l+r>>1; tree[q]=tree[p]; if (val<=mid) tree[q].lc=Insert(tree[p].lc,l,mid,val); //插入到左边，所以只有左儿子改变，其他沿用p点 if (val>mid) tree[q].rc=Insert(tree[p].rc,mid+1,r,val); //插入到右边，所以只有右儿子改变，其他沿用p点 pushup(q); //更新新增点 return q; } int query(int p,int q,int l,int r,int k) { //在p版本和q版本线段树查找[l,r]第k小 if (l==r) return a[l]; int mid=l+r>>1; int tmp=tree[tree[q].lc].sum-tree[tree[p].lc].sum; if (k<=tmp) return query(tree[p].lc,tree[q].lc,l,mid,k); //pq版本通史左跳 if (k>tmp) return query(tree[p].rc,tree[q].rc,mid+1,r,k-tmp); //pq版本同时右跳 } int main() { scanf("%d%d",&n,&q); root[0]=Build(1,n); //先建一棵空树 for (int i=1;i<=n;i++) scanf("%d",&a[i]); memcpy(b,a,sizeof(a)); sort(a+1,a+n+1); tot=unique(a+1,a+n+1)-(a+1); for (int i=1;i<=n;i++) { int x=lower_bound(a+1,a+tot+1,b[i])-a; root[i]=Insert(root[i-1],1,tot,x); //逐个插入数并保留历史版本 } for (int i=1;i<=q;i++) { int l,r,k; scanf("%d%d%d",&l,&r,&k); printf("%d ",query(root[l-1],root[r],1,tot,k)); } return 0; }