主席树学习笔记

## 主席树学习笔记 主席树，即可持久化权值线段树。 本文默认读者已经会了普通的[线段树](https://www.luogu.org/blog/c2522943959/ji-chu-xian-duan-shu) ### 什么是权值线段树？ 一般的线段树维护的是一个序列，节点的权值权值是区间的sum/min/max..... 比如：  （方括号内的是节点“管理的”下标或区间） 而权值线段树维护的是一个区间内数的出现次数，节点的权值是它“管理的”区间内的数的出现次数 比如，对序列`1 3 3 3 4 5 8`建立的权值线段树是这样的 （方括号内的是节点“管理的”值或值域，红色的数字是出现次数） 如果要查询**全局**第$k$小，则可以从根开始这样做： - 当前节点是叶子节点：返回当前节点“管理的”值 - 如果左区间的数出现次数$\leq k$个，那么就从左区间找第$k$小 - 否则，从右区间找第 $k-$左区间的数出现次数 小 显然单次查询的复杂度是$O(logn)$,这也是一种常用的线段树上二分 ~~虽然好像排序也行~~ ### 什么是可持久化？ 没有找到严格的定义，那就我自己扯两句： **允许查询历史版本的数据结构称为可持久化数据结构** 比如说，我给一个可持久化线段树进行了三次区间加之后，还可以查询在第一次区间加后的任何元素/区间的值。（显然普通的线段树做不到这一点） 你可能会问，保存所有历史版本岂不是空间爆炸？ 于是**动态开点**出现了——只保存必须用到的节点，或者说，随用随开。 比如说对序列`1 3 1000001`建立的权值线段树中,显然3~1000001之间的节点都没有被用到，就不需要给这些节点分配空间了 ### 最后，主席树 主席树功能很多，之一便是[查询静态区间第k小](https://www.luogu.org/problem/P3834) 在“查询静态区间第k小”这个功能中，主席树对于序列中的每一个数的加入建立一个历史版本（即，第i个版本表示对[1,i]中所有数构成的序列的权值线段树）（先对第0个版本建立完整的区间线段树，但对于之后每个历史版本，一开始只要存一个根即可） 然后加入$n$个数：从根开始往下走，对于每个节点： - 叶子节点：点权在前一个版本的基础上+1 - 普通节点：先赋值为前一个版本的同位置节点，然后如果要修改的点在左区间，就为左区间申请一个空间并递归处理左区间。如果在右区间同理。 上文提到，权值线段树可以求解**全局**第$k$小。 那如何查询**区间**第$k$小呢？ 显然，用历史版本$r$减去历史版本$l-1$剩下的权值线段树可以查询。 但是，虽然查询的复杂度是$O(logn)$,但是这个历史版本相减的复杂度……是$O(n)$啊。 别紧张，和上面动态开点的思想是一样的：只保存必须用到的节点。于是乎，复杂度就变成非常优秀的$O(logn)$每次了。 甚至，在实现的时候，这个“历史版本$r$减去历史版本$l-1$剩下的权值线段树”不用显式的建出来。（可详见代码） 最后，主席树建立的时间复杂度是$O(nlogn)$,空间复杂度是$O(nlogn)$,单次查询的时间复杂度是$O(logn)$ Code: （普通的线段树数组实现也行，但主席树用指针实现更美） ```cpp //Wan Hong 2.2 //home #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> typedef long long ll; typedef unsigned un; typedef std::string str; #define INF (1ll<<58) ll read() { char c; ll f=1,x=0; do { c=getchar(); if(c=='-')f=-1; }while(c<'0'||c>'9'); do { x=x*10+c-'0'; c=getchar(); }while(c>='0'&&c<='9'); return f*x; } ll max(ll a,ll b) { return a>b?a:b; } ll min(ll a,ll b) { return a<b?a:b; } /**********/ #define MAXN 200011 struct node//每个节点维护的信息 { node *tl,*tr; ll v; }dizhi[MAXN*21+1],*root[MAXN];//注意，主席树的空间是nlogn的 ll n,m,cnt=0; void build(node* rt,un l=1,un r=n)//第0个版本要建完整的 { if(l==r) { rt->v=0;return; } un mid=(l+r)>>1; rt->tl=dizhi+(++cnt); rt->tr=dizhi+(++cnt); build(rt->tl,l,mid);build(rt->tr,mid+1,r); rt->v=rt->tl->v+rt->tr->v; } void modify(node* last,node* rt,un p,ll x,un l=1,un r=n)//基于last（前一个版本）将位置p加上x { if(l==r) { rt->v=last->v+x; return; } *rt=*last; un mid=(l+r)>>1; if(p<=mid) { rt->tl=dizhi+(++cnt);//动态开点 modify(last->tl,rt->tl,p,x,l,mid); } else { rt->tr=dizhi+(++cnt);//动态开点 modify(last->tr,rt->tr,p,x,mid+1,r); } rt->v=rt->tl->v+rt->tr->v; } ll query(node* last,node* rt,un k,un l=1,un r=n)//询问 { if(l==r)return l; un mid=(l+r)>>1,tmp=(rt->tl->v)-(last->tl->v);//这样做就是“隐式建树” if(k<=tmp)return query(last->tl,rt->tl,k,l,mid); else return query(last->tr,rt->tr,k-tmp,mid+1,r); } struct disc//这几行是离散化 { ll v,num,rk; }a[MAXN]; bool cmp1(disc a,disc b) { return a.v<b.v; } bool cmp2(disc a,disc b) { return a.num<b.num; } ll fx[MAXN]; int main() { n=read(),m=read(); for(ll i=0;i<=n;++i)root[i]=dizhi+(++cnt);//为每个版本的根分配空间 build(root[0]); for(ll i=1;i<=n;++i) { a[i].v=read(); a[i].num=i; } std::sort(a+1,a+n+1,cmp1); ll it=0; for(ll i=1;i<=n;++i) { a[i].rk=++it; fx[it]=a[i].v; while(a[i].v==a[i+1].v)a[++i].rk=it; } std::sort(a+1,a+n+1,cmp2); for(ll i=1;i<=n;++i) modify(root[i-1],root[i],a[i].rk,1); for(ll i=1;i<=m;++i) { ll l=read(),r=read(),k=read(),ans=query(root[l-1],root[r],k); printf("%lld\n",fx[ans]); } return 0; } ``` 任何疑问，请评论或私信我