可持久化线段树 1（主席树）

## [更多主席树内容可见原文](https://www.cnblogs.com/bcoier/p/10293521.html) PS：由于篇幅较长，只给出模板题代码，其他代码详见上述连接 主席树，一个数据结构，能访问到历史版本的数据，常用于可持久化和区间k大值，是线段树的一个升级版。 ## 可持久化 可持久化的意思是可以访问任意版本的数据，一眼想到的暴力做法就是开n个数组来记录，这显然是不可取的。 那么我们考虑优化。若只有单点修改，不难发现每两个版本的差别最多为1，那么我们是不是可以只更改只一个数呢？ ~~显然是可以的。~~在线段树上，我们每访问到一个节点，如果该节点没有被修改，直接用指针指想该节点即可（和动态开点线段树类似） 要注意的是，我们不能像以前一样用$k*2$表示左儿子，$k*2+1$表示右儿子了（如果你用动态开点就当我没说），而是要用指针来访问左右儿子。 那我们怎么访问每一个版本呢？我们只需要对每一个版本存储一个根节点，从根节点访问就行了 这样我们就可以很好的来处理可持久化的问题了。 ## [例题1-可持久化数组](https://www.luogu.org/problemnew/show/P3919) 直接采用上述方法，维护每一个版本的root即可 有了可持久化数组，那么我们便可以操作其他可持久化数据结构，如可持久化并查集 ## [例题2-可持久化并查集](https://www.luogu.org/problemnew/show/P3402) 我们把每一个版本的fa数组记录下来，就可以很好的查询历史版本了。我们发现对于每次合并，fa数组只会修改一个（不能用路径压缩，因为路径压缩一次会修改很多值），所以我们直接用上述方法做就行了。 如果直接修改，那么单次复杂度可能退化成O(n)，所以我们可以用启发式合并或按秩合并 ## 区间k大 ~~我们知道~~，[权值线段树](https://www.cnblogs.com/zmyzmy/p/9529234.html)是可以求全局k大的，那么我们可不可以用权值线段树来实现区间k大呢？ ~~显然是可以的。~~我们可以先考虑1~l区间的k大。 我们给每一个点开一颗前缀的权值线段树，那么我们就可很容易的求出1~l的第k大值了。但是常规做法显然会炸空间，所以我们采用可持久化的方法来动态开点 那么区间k大怎么做呢？ 这就要用到权值线段树的可减性。（权值线段树维护的是每个元素的出现个数，这显然是可减的） 于是对于段区间，我们看成连段区间相减就行了。 ## [例题2-可持久化线段树](https://www.luogu.org/problemnew/show/P3834) 代码如下 ``` #include<bits/stdc++.h> using namespace std; #define re register #define il inline il int read() { re int x=0,f=1;re char c=getchar(); while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') x=x*10+c-48,c=getchar(); return x*f; } #define maxn 200005 struct node { int l,r,val; }e[maxn*20]; int n,m,root[maxn],cnt,b[maxn],a[maxn],co; il void build(int &k,int l,int r) { k=++cnt; if(l==r) return; int mid=(l+r)>>1; build(e[k].l,l,mid),build(e[k].r,mid+1,r); } il void change(int &k,int kk,int l,int r,int ll) { k=++cnt; e[k]=e[kk]; e[k].val++; if(l==r) return; int mid=(l+r)>>1; if(ll<=mid) change(e[k].l,e[kk].l,l,mid,ll); else change(e[k].r,e[kk].r,mid+1,r,ll); } il int query(int ll,int rr,int l,int r,int k) { int x=e[e[rr].l].val-e[e[ll].l].val; if(l==r) return b[l]; int mid=(l+r)>>1; if(x>=k) return query(e[ll].l,e[rr].l,l,mid,k); return query(e[ll].r,e[rr].r,mid+1,r,k-x); } int main() { n=read(),m=read(); for(re int i=1;i<=n;++i) a[i]=b[i]=read(); sort(b+1,b+n+1);//排序 co=unique(b+1,b+n+1)-b-1;//去重 build(root[0],1,co); for(re int i=1;i<=n;++i) { int now=lower_bound(b+1,b+co+1,a[i])-b;//意思是找到和a[i]相等的b，这样做的目的是保证所有的相等的全值都能保证被分到一个下标 change(root[i],root[i-1],1,co,now);//因为是前缀权值线段树，所以在前一刻子树的基础上修改 } while(m--) { int l=read(),r=read(),k=read(); printf("%d\n",query(root[l-1],root[r],1,co,k)); } return 0; } ``` ## [不那么模板的模板题](https://www.luogu.org/problemnew/show/P2633) 这题是强制在线，所以不能用整体二分等离线做法水过去，所以我们用主席树。 拓展到了树上，所以我们可以进行dfs，把上一题的建树过程改成change(root[i],root[fa[i]],1,co,now)即可 最后统计答案，我们不能直接用r的权值线段树-l的权值线段树，而使用l+r-lca(l,r)-fa[lca(l,r)]（这里表示权值线段树），正确性类似于树上差分，在此不再赘述。 由于要求LCA，且要用dfs，所以我直接用树剖来求lca，将树剖的dfs1和要求的dfs合并在一起就行了。