主席树与带修改主席树

主席树与带修改主席树

主席树

简单介绍

主席树是可持久化线段树的一种,为什么叫主席树呢?网上说法很多,我也不知道为什么QAQ,有兴趣的同学可以自己去查找,这里就不讲了。

主席树可以看做多棵线段树,在1~n每个点i(1<=i<=n)建一棵线段树,来记录1~i的状态。每棵线段树区间[L,R]表示从1~i中权值在[l,r]中的数出现了几次。然后用于寻找区间第K大。

怎么找区间第K大呢?我们套用差分的思想,进行树的前缀和,然后树上对应位置相减,就是这个位置为根的子树在给出区间的状态。这里可能有点难理解,看代码就可以知道怎么求这个前缀和了。

对于每一个点建一棵线段树,空间肯定存不下,那么怎么办呢?

我们会发现第i棵线段树和第i-1棵线段树,只有从[1,maxW_i][W_i,W_i],这条链改变了,其余节点都没有改变,所以我们可以建一棵动态开点线段树,然后没有改变的地方就和上一棵线段树共用,这样空间复杂度就是n log_2 (maxW_i)了,大大优化了空间。

普通主席树是离线的,不允许修改,如果带修改的话,就得写树套树了。(下面会讲)

例题

洛谷P3834

代码如下

首先介绍一下变量:

struct xcw{int L,R,x;}Tre[MAXN<<5];//动态开点线段树
int a[MAXN],n,m;//读入的数据
int hsh[MAXN];//离散
int T[MAXN];//T[i]第i个点的线段树的根的位置
int K;//maxWi
int tot;//计数器,用于动态开点线段树

其实和动态开点线段树没什么两样。

过程

我们先不管函数怎么写,假设我们已经写好了。

n=read(),m=read();
for(int i=1;i<=n;i++) hsh[i]=a[i]=read();//离散,因为数据跨度有点大,但是不离散也可以,就是数组要开大。
sort(hsh+1,hsh+1+n);
K=unique(hsh+1,hsh+1+n)-hsh-1;
T[0]=Build(1,K);//这棵线段树的区间就是1~K
for(int i=1;i<=n;i++){
    int x=lower_bound(hsh+1,hsh+1+K,a[i])-hsh;
    T[i]=Updata(1,K,T[i-1],x);//做树的前缀和,肯定要加上前一棵树的值
}
while(m--){
    int L=read(),R=read(),k=read();
    printf("%d\n",hsh[Ask(T[L-1],T[R],1,K,k)]);//差分的想法[R]-[L-1]。
}

建树

不建议写,因为我们可以吧0号节点看成一棵线段树,如果建树的话,浪费空间。

int Build(int L,int R){
    int now=++tot;
    if(L<R){
        int mid=(R+L)>>1;
        Tre[now].L=Build(L,mid);
        Tre[now].R=Build(mid+1,R);
    }
    return now;
}

再次强调,不建议写,只是方便理解。

插入

我们要做树的前缀和,那么肯定要从前一棵树转移过来,所以我们还要用last变量表示前一棵树的对应位。

int Updata(int L,int R,int rot,int x){//这里rot就是last,rot跟当前的点一起走,不过是走前一棵树罢了。
    int now=++tot;
    Tre[now].L=Tre[rot].L,Tre[now].R=Tre[rot].R,Tre[now].x=Tre[rot].x+1;
    if(L<R){
        int mid=(R+L)>>1;
        if(x<=mid) Tre[now].L=Updata(L,mid,Tre[rot].L,x);//同时往相同子树走
        else Tre[now].R=Updata(mid+1,R,Tre[rot].R,x);
    }
    return now;
}

查询

和插入一样,两个指针同时动。

int Ask(int u,int v,int L,int R,int k){
    if(L>=R) return L;
    int mid=(R+L)>>1,num=Tre[Tre[v].L].x-Tre[Tre[u].L].x;
    //num表示左子树中元素个数
    if(num>=k) return Ask(Tre[u].L,Tre[v].L,L,mid,k);//表示第k大的数在左子树中
    else return Ask(Tre[u].R,Tre[v].R,mid+1,R,k-num);
    //表示第k大的数在右子树中,注意要查找的数在右子树中的排名为k-num
}

然后就结束了

全部代码

#include<cstdio>
#include<cctype>
#include<algorithm>
#define MAXN 200005
using namespace std;
int a[MAXN],n,m,hsh[MAXN],T[MAXN],K,tot;
struct xcw{int L,R,x;}Tre[MAXN<<5];
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret<<3)+(ret<<1)+ch-48;
    return f?ret:-ret;
}
int Build(int L,int R){
    int now=++tot;
    if(L<R){
        int mid=(R+L)>>1;
        Tre[now].L=Build(L,mid);
        Tre[now].R=Build(mid+1,R);
    }
    return now;
}
int Updata(int L,int R,int rot,int x){
    int now=++tot;
    Tre[now].L=Tre[rot].L,Tre[now].R=Tre[rot].R,Tre[now].x=Tre[rot].x+1;
    if(L<R){
        int mid=(R+L)>>1;
        if(x<=mid) Tre[now].L=Updata(L,mid,Tre[rot].L,x);
        else Tre[now].R=Updata(mid+1,R,Tre[rot].R,x);
    }
    return now;
}
int Ask(int u,int v,int L,int R,int k){
    if(L>=R) return L;
    int mid=(R+L)>>1,num=Tre[Tre[v].L].x-Tre[Tre[u].L].x;
    if(num>=k) return Ask(Tre[u].L,Tre[v].L,L,mid,k);
    else return Ask(Tre[u].R,Tre[v].R,mid+1,R,k-num);
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    n=read(),m=read();
    for(int i=1;i<=n;i++) hsh[i]=a[i]=read();
    sort(hsh+1,hsh+1+n);
    K=unique(hsh+1,hsh+1+n)-hsh-1;
    T[0]=Build(1,K);
    for(int i=1;i<=n;i++){
        int x=lower_bound(hsh+1,hsh+1+K,a[i])-hsh;
        T[i]=Updata(1,K,T[i-1],x);
    }
    while(m--){
        int L=read(),R=read(),k=read();
        printf("%d\n",hsh[Ask(T[L-1],T[R],1,K,k)]);
    }
    return 0;
} 

是不是很简单?

带修改主席树

(作者正在复习中)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部