Posted at 2019-07-26 ICPC

主席树的原理及使用

0.前置知识

需要掌握线段树

1. 原理

主席树即“可持久化线段树”，是存储每次修改时线段树状态的线段树，由于存储了每次的状态，所以可以进行对过去状态的回溯。

目前来看，主席树除了可以解决对线段树的过去状态进行询问的问题，还能解决区间第K大即区间最值的快速查询，单次查询的时间复杂度是O(log₂n)。整个主席树的空间复杂度可以达到O(2n+mlog₂n),前面的2n是线段树的大小，后面的是每次修改增加的点数。对于每次修改，主席树需要把路径上经过的所有点进行修改并重新存储。嘛总之空间复杂度高的话开到20*maxn吧，由于主席树单个点的结构还挺简单的，这样往往也不会爆。

那么要如何来构建一个主席树呢？

如果只是存储过去的线段树，那主席树还挺好写的，同线段树一样，先pre_build一个线段树，(但是注意要存储节点的左右儿子，来紧凑增加点，不然后面的新树可能会覆盖旧节点)，然后每次对线段树的修改，都新建一个根节点，存储修改的每个点，上面也是这么说的就不再赘述了。

但是求区间第k大的过程还是很有趣的。此时我们转换思路，将每个点的值看作是一次插入，而初始的线段树是只有一个根节点的空树，或者说是一棵叶子节点从1到INF的树。每个点的左右边界 [ l,r ]就代表着值为 [ l,r ]的点有多少。这种线段树在正常情况下是肯定构造不出来的，我们平时都是左右边界代表序号而权值代表编号的值，但由于区间中的点都很离散，所以用主席树这样动态建点实际上是非常节省空间的，每次只增加log₂(INF)的节点，即最多32个。这样在每次寻找第k大的时候，我们只需要比较左右儿子区间中包含的点数与k的关系即可。

2.具体题目

HDU-2665 Kth number - 区间第K小问题

这个题题面说是第K大，就很菜，实际上是个第K小。

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
//结果这个题目骗我，自己明明是第K小
typedef long long LL;
const int maxn=100005;
struct Node{
    int ls,rs,sum;
//求第k大的时候不需要区间信息就不存左右节点了
//正常情况下还是要像正常线段树一样存的
    Node(int l,int r):ls(l),rs(r){}
    Node(){}
}tree[maxn*20];
int coun,root[maxn];
void tree_insert(int num,int &k,int l,int r){
    tree[++coun]=tree[k];//先新建点继承原先的数据
    k=coun;//主要是为了修改父节点的左右儿子的值
    tree[k].sum++;//更新一下数据，如果有别的也要更新别的
    if(l==r) return ;//到叶子节点了
    int mid=(l+r)>>1;
    if(num<=mid)
        tree_insert(num,tree[k].ls,l,mid);
    else tree_insert(num,tree[k].rs,mid+1,r);
}
int query(int before,int after,int k,int l,int r){
    //before 与after 存储的是前后两个线段树的头节点
    if(l==r) return l;
    int leftadd=tree[tree[after].ls].sum-tree[tree[before].ls].sum;
    int mid=(l+r)>>1;
    if(k<=leftadd)
        query(tree[before].ls,tree[after].ls,k,l,mid);
    else query(tree[before].rs,tree[after].rs,k-leftadd,mid+1,r);
}
int n,m,ori[maxn],discrete[maxn];
int main(void)
{
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        tree[0].sum=tree[0].ls=tree[0].rs=0;
        root[0]=0;
        for(int i=1;i<=n;++i){
            scanf("%d",&ori[i]);
            discrete[i]=ori[i];
        }
        coun=0;
        sort(discrete+1,discrete+n+1);
        int newn=unique(discrete+1,discrete+n+1)-discrete-1;
        for(int i=1;i<=n;++i){
            ori[i]=lower_bound(discrete+1,discrete+newn+1,ori[i])-discrete;
            root[i]=root[i-1];
            tree_insert(ori[i],root[i],1,newn);
        }
        int s,t,k,res;
        for(int i=0;i<m;++i){
            scanf("%d%d%d",&s,&t,&k);
            res=query(root[s-1],root[t],k,1,newn);
            printf("%d\n",discrete[res]);
        }

    }
    return 0;
}

HDU-6601 Keen On Everything But Triangle 区间第k大

题目看似是让你找能形成三角形的边，实际上就是在一个区间里从最大的边开始往下贪心。构不成三角形的最坏情况就是Fibonacci数列，Fibonacci数列递增的又很快，所以最多的情况是44个数都不能形成三角形，复杂度O(44*logn)，完全可以接受。

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
const int maxn=100005;
//正好用主席树试试吧
struct node{
    int ls,rs,sum;
}tree[maxn*20];
int root[maxn],tot;
void tree_insert(int num,int &k,int l,int r){
    tree[++tot]=tree[k];k=tot;
    ++tree[k].sum;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(num<=mid) tree_insert(num,tree[k].ls,l,mid);
    else tree_insert(num,tree[k].rs,mid+1,r);
}
int query_big(int bef,int aft,int l,int r,int k){
    if(l==r) return l;
    int rightadd=tree[tree[aft].rs].sum-tree[tree[bef].rs].sum;
    int mid=(l+r)>>1;
    if(k<=rightadd)
        return query_big(tree[bef].rs,tree[aft].rs,mid+1,r,k);
    else
        return query_big(tree[bef].ls,tree[aft].ls,l,mid,k-rightadd);
}
int ori[maxn];
LL lisj[maxn];

int main(void)
{
    //freopen("1011.in","r",stdin);
    //freopen("test.txt","w",stdout);
    int n,q;
    while(~scanf("%d%d",&n,&q)){
        tree[0].ls=tree[0].rs=tree[0].sum=0;
        root[0]=0;
        tot=0;
        for(int i=1;i<=n;++i){
            scanf("%d",&ori[i]);
            lisj[i]=ori[i];
        }
        sort(lisj+1,lisj+1+n);
        int newn=unique(lisj+1,lisj+n+1)-lisj-1;
        for(int i=1;i<=n;++i){
            ori[i]=lower_bound(lisj+1,lisj+1+newn,ori[i])-lisj;
            root[i]=root[i-1];
            tree_insert(ori[i],root[i],1,newn);
        }
        LL line[5];
        while(q--){
            int l,r;
            scanf("%d%d",&l,&r);
            line[0]=line[1]=line[2]=0;
            LL res=-1;
            for(int i=0;i<r-l+1;++i){
                line[i%3]=query_big(root[l-1],root[r],1,newn,i+1);
                LL a=lisj[line[i%3]],b=lisj[line[(i+2)%3]],c=lisj[line[(i+1)%3]];
                if(i>=2&&a+b>c){
                    res=a+b+c;
                    break;
                }
            }
            printf("%lld\n",res);
        }
    }
    return 0;
}

HDU-4348 To the moon 区间修改

题目一读就知道是版题呢，都告诉你要回溯了。这个题跟上面两个的不同就在于必须先建树，而不是像上面那样边插入点边建。同时建树不能按照线段树的二进制思想建，因为二进制思想建虽然方便但是中间会有空间的空隙，放在主席树当中这些空隙会让你不知道往哪放新建的点。

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
const int maxn=100005;
struct node{
    LL lazy,sum;
    int ls,rs;
}tree[maxn*20];
int root[maxn],tot,timestamp;
//kl kr用来标记区间
LL ori[maxn], sum[maxn];;
void pre_build(int k,int l,int r){

    tree[k].lazy=0;
    tree[k].sum=sum[r]-sum[l-1];
    if(l==r) return;
    tree[k].ls=++tot;
    tree[k].rs=++tot;
    int mid=(l+r)>>1;
    pre_build(tree[k].ls,l,mid);
    pre_build(tree[k].rs,mid+1,r);
}
void tree_insert(int kl,int kr,int l,int r,int &k,LL val){
    tree[++tot]=tree[k];
    k=tot;

    if(l==kl&&r==kr) {
        tree[k].lazy+=val;
        return;
    }
    else tree[k].sum+=val*(r-l+1);
    int mid=(kl+kr)>>1;
    if(r<=mid) tree_insert(kl,mid,l,r,tree[k].ls,val);
    else if(l>mid) tree_insert(mid+1,kr,l,r,tree[k].rs,val);
    else {
        tree_insert(kl,mid,l,mid,tree[k].ls,val);
        tree_insert(mid+1,kr,mid+1,r,tree[k].rs,val);
    }
}
LL query(int kl,int kr,int l,int r,int k){
    LL res=tree[k].lazy*(r-l+1);
    int mid=(kl+kr)>>1;
    if(kl==l&&kr==r) return res+tree[k].sum;
    if(r<=mid) res+=query(kl,mid,l,r,tree[k].ls);
    else if(l>mid) res+=query(mid+1,kr,l,r,tree[k].rs);
    else res+=query(kl,mid,l,mid,tree[k].ls)+query(mid+1,kr,mid+1,r,tree[k].rs);
    return res;

}

int n,m;
int main(void)
{
    sum[0]=0;
    while(~scanf("%d%d",&n,&m)){
        memset(root,0,sizeof(root));
        tree[0].sum=tree[0].lazy=tree[0].ls=tree[0].rs=0;
        for(int i=1;i<=n;i++){
            scanf("%lld",&ori[i]);
            sum[i]=sum[i-1]+ori[i];
        }
        timestamp=tot=0;
        pre_build(++tot,1,n);
        root[0]=1;
        char ch;
        int a,b;
        LL c;
        while(m--){
            scanf("%c",&ch);
            while(ch!='C'&&ch!='H'&&ch!='Q'&&ch!='B')scanf("%c",&ch);
            if(ch=='C'){
                scanf("%d%d%lld",&a,&b,&c);
                ++timestamp;
                root[timestamp]=root[timestamp-1];
                tree_insert(1,n,a,b,root[timestamp],c);
            }
            else if(ch=='Q'){
                scanf("%d%d",&a,&b);
                LL res=query(1,n,a,b,root[timestamp]);
                printf("%lld\n",res);
            }
            else if(ch=='H'){
                scanf("%d%d%lld",&a,&b,&c);
                LL res=query(1,n,a,b,root[c]);
                printf("%lld\n",res);
            }
            else if(ch=='B'){
                scanf("%d",&timestamp);
                root[timestamp+1]==0?:tot=root[timestamp+1];
            }

        }
    }
    return 0;
}

Previous post: sup-extra 代码模板 Next post: sup-004 Docker环境搭建与开发入门

Site-T

SUP-project