主席树学习笔记

 

　　　　　　　　　　　　　　　　　　　　　　　主席树

主席树就是线段树的优化

先来看模板题:

野生动物园

 

就是求区间$k$大值，

我们先将每个数的权值离散化，再建$n$棵权值线段树,

针对l-r里的权值就通过前缀和减一下就好了,

但这样空间复杂度是$o(n^2)$的，

考虑优化：

每次新建一颗线段树就最多只会出现$logn$个新节点，于是我们把新的和旧的拼接起来即可

至于寻找k大值，因为前缀和存在单调性，直接用分治的思想来找即可$O(logn)$

总体流程:

1.将所有数离散化

2.建议一棵空的线段树

3.每一次把一个点与线段树连边，多加上$logn$个点

4.利用分治来找最大值

注意:由于有$nlogn$个节点，线段树数组必须开$nlogn$个，一般来说是$n<<5$

代码:

建树

void build(int l,int r) {
    int p=++cnt;
    int mid=(l+r)/2;
    if(l==r) return;
    build(l,mid);
    build(mid+1,r);
}

加点

int add(int x,int l,int r) {
    int p=++cnt;
    t[p].l=t[x].l,t[p].r=t[x].r,t[p].sum=t[x].sum+1;
    if(l==r) return p;
    int mid=(l+r)/2;
    if(mid>=rk) t[p].l=add(t[p].l,l,mid);
    else t[p].r=add(t[p].r,mid+1,r);
    return p;
}

查询

int ask(int x,int p,int l,int r,int rk) {
    int num=t[t[p].l].sum-t[t[x].l].sum;
    int mid=(l+r)/2;
    if(l==r) return l;
    if(num>=rk) return ask(t[x].l,t[p].l,l,mid,rk);
    else return ask(t[x].r,t[p].r,mid+1,r,rk-num);
}

总代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int rt[N],a[N],b[N],cnt,rk,n,m;
struct data {
    int l,r,sum;
} t[N<<5];
void build(int l,int r) {
    int p=++cnt;
    int mid=(l+r)/2;
    if(l==r) return;
    build(l,mid);
    build(mid+1,r);
}
int add(int x,int l,int r) {
    int p=++cnt;
    t[p].l=t[x].l,t[p].r=t[x].r,t[p].sum=t[x].sum+1;
    if(l==r) return p;
    int mid=(l+r)/2;
    if(mid>=rk) t[p].l=add(t[p].l,l,mid);
    else t[p].r=add(t[p].r,mid+1,r);
    return p;
}
int ask(int x,int p,int l,int r,int rk) {
    int num=t[t[p].l].sum-t[t[x].l].sum;
    int mid=(l+r)/2;
    if(l==r) return l;
    if(num>=rk) return ask(t[x].l,t[p].l,l,mid,rk);
    else return ask(t[x].r,t[p].r,mid+1,r,rk-num);
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    int q=unique(b+1,b+n+1)-b-1;
    rt[0]=1;
    build(1,q);
    for(int i=1; i<=n; i++) {
        rk=lower_bound(b+1,b+q+1,a[i])-b;
        rt[i]=add(rt[i-1],1,q);
    }
    for(int i=1,l,r,k; i<=m; i++) {
        scanf("%d%d%d",&l,&r,&k);
//    cout<<ask(rt[l-1],rt[r],1,q,k)<<endl;
        printf("%d
",b[ask(rt[l-1],rt[r],1,q,k)]);
    }
    return 0;
} 

还有一道比较好的题:

middle

我们可以二分枚举中位数,大于$mid$的数,大于$mid$的数权值赋值为$1$,小于$mid$的数权值赋值为$-1$

针对每个$mid$在线段树里找最大子段和,若最大子段和$>=0$,则合法

因为每次你增加$mid$，只会修改一个数,所以能用主席树

$code$:

#include<bits/stdc++.h>
using namespace std;
const long long N=2e4+10;
struct data {
    long long id,x;
} b[N];
struct Query {
    long long a,b,c,d;
} Q[N+5*1000];
struct segment_tree {
    long long lmax,sum,rmax,l,r;
} t[N*100];
bool cmp(data c,data d) {
    return c.x<d.x;
}
long long rt[N],cnt,n,m,last_ans,pos[5];
void update(long long p) {
    t[p].sum=t[t[p].l].sum+t[t[p].r].sum;
    t[p].lmax=max(t[t[p].r].lmax+t[t[p].l].sum,t[t[p].l].lmax);
    t[p].rmax=max(t[t[p].l].rmax+t[t[p].r].sum,t[t[p].r].rmax);
//cout<<t[p].sum<<" ";
}
void build(long long &p,long long l,long long r) {
    p=++cnt;
    if(l==r) {
        t[p].sum=1;
        t[p].lmax=1;
        t[p].rmax=1;
        return;
    }
    long long mid=(l+r)>>1;
    build(t[p].l,l,mid);
    build(t[p].r,mid+1,r);
    update(p);
}
long long change(long long x,long long l,long long r,long long k) {
    long long p=++cnt;
    t[p]=t[x];
    if(l==r) {
        t[p].sum=t[p].lmax=t[p].rmax=-1;
        return p;
    }
    long long mid=(l+r)>>1;
    if(k<=mid)
        t[p].l=change(t[p].l,l,mid,k);
    else    t[p].r=change(t[p].r,mid+1,r,k);
    update(p);
    return p;
}
long long query_sum(long long p,long long l,long long r,long long x,long long y) {
    if(x<=l&&r<=y)
        return t[p].sum;
    long long mid=(l+r)>>1;
    long long ans=0;
    if(x<=mid)
        ans+=query_sum(t[p].l,l,mid,x,y);
    if(y>mid)
        ans+=query_sum(t[p].r,mid+1,r,x,y);
    return ans;
}
long long query_lmax(long long p,long long l,long long r,long long x,long long y) {
    if(x<=l&&r<=y)
        return t[p].lmax;
    long long mid=(l+r)>>1;
    if(y<=mid)
        return query_lmax(t[p].l,l,mid,x,y);
    if(x>mid)
        return query_lmax(t[p].r,mid+1,r,x,y);
    if(x<=mid&&y>mid)
        return max(query_lmax(t[p].l,l,mid,x,mid),query_sum(t[p].l,l,mid,x,mid)+query_lmax(t[p].r,mid+1,r,mid+1,y));
}
long long query_rmax(long long p,long long l,long long r,long long x,long long y) {
    if(x<=l&&r<=y) return t[p].rmax;
    long long mid=(l+r)>>1;
    if(y<=mid)
        return query_rmax(t[p].l,l,mid,x,y);
    if(x>mid)
        return query_rmax(t[p].r,mid+1,r,x,y);
    if(x<=mid&&y>mid)
        return max(query_rmax(t[p].r,mid+1,r,mid+1,y),query_sum(t[p].r,mid+1,r,mid+1,y)+query_rmax(t[p].l,l,mid,x,mid));
}
long long check(long long x) {
    long long t1=0;
    if(pos[3]-1-pos[2]>0)
        t1=query_sum(rt[x],1,n,pos[2]+1,pos[3]-1);
    long long t2=query_lmax(rt[x],1,n,pos[3],pos[4]);
    long long t3=query_rmax(rt[x],1,n,pos[1],pos[2]);
//    cout<<x<<" "<<t1<<" "<<t2<<" "<<t3<<endl;
    return (t1+t2+t3)>=0;
}
long long paepare_query() {
    long long l=1,r=n;
    while(l<r) {
        long long mid=(l+r+1)>>1;
        if(check(mid))l=mid;
        else r=mid-1;
    }
    return b[l].x;
}
int main() {
    scanf("%lld",&n);
    for(long long i=1; i<=n; i++)scanf("%lld",&b[i].x),b[i].id=i;
    sort(b+1,b+n+1,cmp);
    build(rt[1],1,n);
    for(long long i=2; i<=n; i++)rt[i]=change(rt[i-1],1,n,b[i-1].id);
    scanf("%lld",&m);
    for(long long i=1; i<=m; i++)scanf("%lld%lld%lld%lld",&Q[i].a,&Q[i].b,&Q[i].c,&Q[i].d);
    for(long long i=1; i<=m; i++) {
        pos[1]=(Q[i].a+last_ans)%n+1,pos[2]=(Q[i].b+last_ans)%n+1,pos[3]=(Q[i].c+last_ans)%n+1,pos[4]=(Q[i].d+last_ans)%n+1;
        sort(pos+1,pos+4+1);
        printf("%lld
",last_ans=paepare_query());
    }
    return 0;
}

总结:当我们要建$n$可线段树时，且这$n$棵线段树的权值是递增的，就可以用主席树来省空间

完结撒花