主席树模板

@zryabc  January 10, 2019

概念

主席树,又名可持久化线段树,是解决区间第k大问题的利器。其原理是运用函数化思想,在每一个点上都构建一课[1,i]的线段树,线段树中存的是数值而不是下标。

基本思想

我们先思考一个会MLE&TLE的解法:

对于每个点,构建一棵[1,i]线段树,存放[1,i]的所有$A[i]$,比如说前三个数为1,3,2,则这棵线段树如下图:

graph TD
1-->2
2-->4
2-->5
1-->3

每个节点对应着一个区间,我们同时再记录一个$sum[i]$表示当前编号的点底下有多少元素。

这样的线段树满足作差的性质,如果我们要求$[l,r]$区间的第k大值,我们很容易得到,只要将两棵线段树的节点作差,并可以知道$[l,r]$区间内每个值出现的次数,于是就可以在树上二分了。

然而,如果真的这样搞的话,在建树的过程中就已经MLE&TLE了。

优化策略

所以,主席树最精髓的一点就在于时间和空间上的优化。

我们注意到,如果真的建了n棵线段树,那么很多节点其实是重复的,那我们能不能让一些树共用一些节点呢?

注意到,对于新加的一个节点来说,它沿途所走过的点最多只有logn个,换而言之,我们只需要重新建logn个节点就可以再完成一棵线段树了。这就是主席树的精髓。

最后我们开个$ver[i]$表示每棵树的节点编号,问题就解决了。

代码

#include<bits/stdc++.h>
#define M 200005
using namespace std;
int Lson[M*20],Rson[M*20],ver[M],sum[M*20],A[M],tmp[M],tot=0;
struct node{
    int id,x;
    bool operator < (const node& res) const {
        return x<res.x; 
    }
}B[M];
int n,m;
void Insert(int od,int &rt,int x,int L,int R){
    rt=++tot;
    Lson[rt]=Lson[od];
    Rson[rt]=Rson[od];
    sum[rt]=sum[od]+1;
    if(L==R)return;
    int mid=(L+R)>>1;
    if(x<=mid)Insert(Lson[od],Lson[rt],x,L,mid);
    else Insert(Rson[od],Rson[rt],x,mid+1,R); 
}
int query(int l,int r,int L,int R,int k){
    if(L==R)return L;
    int cnt=sum[Lson[r]]-sum[Lson[l]];
    int mid=(L+R)>>1;
    if(k<=cnt)return query(Lson[l],Lson[r],L,mid,k);
    return query(Rson[l],Rson[r],mid+1,R,k-cnt);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)    
        scanf("%d",&B[i].x),B[i].id=i;
    sort(B+1,B+n+1);B[0].x=-2e9;
    int q=0;
    for(int i=1;i<=n;i++){
        if(B[i].x!=B[i-1].x)q++;
        A[B[i].id]=q;
        tmp[q]=B[i].x;
    }
    for(int i=1;i<=n;i++)
        Insert(ver[i-1],ver[i],A[i],1,q);
    while(m--){
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        printf("%d\n",tmp[query(ver[l-1],ver[r],1,q,r-l-k+2)]);
    }
    return 0;
}

添加新评论

  1. 这里解决的问题是区间第K小

    Reply