学习粗：https://blog.csdn.net/creatorx/article/details/75446472

主要解决 可查询历史版本的线段树，区间第k大问题

 

我们询问【L,R】时，我们就认为是第R棵树减去第L-1棵树；（详情：）

 

 

在询问时我们以root[]进行区间查询，因为我们我们在建的时候（update）已经按照分树来做，所以第一步传入的位置正确的话，又因为结构体内已存入左右孩子，所以顺传下去。就是对的，

题1：http://poj.org/problem?id=2104（静态主席树）

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;inline int read(){    int sum=0,x=1;    char ch=getchar();    while(ch<'0'||ch>'9'){        if(ch=='-')            x=0;        ch=getchar();    }    while(ch>='0'&&ch<='9')        sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar();    return x?sum:-sum;}inline void write(int x){    if(x<0)        putchar('-'),x=-x;    if(x>9)        write(x/10);    putchar(x%10+'0');}const int M=1e5+5;struct node{    int sum,L,R;}tree[M*40];int root[M],a[M],b[M],n,m,cnt;void build(int &now,int l,int r){    now=++cnt;    if(l==r)        return ;    int midd=(l+r)>>1;    build(tree[now].L,l,midd);    build(tree[now].R,midd+1,r);}void update(int &rt,int pos,int l,int r){    tree[++cnt]=tree[rt];    tree[cnt].sum++;    rt=cnt;    if(l==r)        return ;    int midd=(l+r)>>1;    if(pos<=midd)        update(tree[rt].L,pos,l,midd);    else        update(tree[rt].R,pos,midd+1,r);}int query(int i,int j,int k,int l,int r){    int num=tree[tree[j].L].sum-tree[tree[i].L].sum;    if(l==r)        return l;    int midd=(l+r)>>1;    if(num>=k)            return query(tree[i].L,tree[j].L,k,l,midd);    else            return query(tree[i].R,tree[j].R,k-num,midd+1,r);}int main(){    n=read(),m=read();    for(int i=1;i<=n;i++)        a[i]=read(),b[i]=a[i];    sort(b+1,b+1+n);    int p=unique(b+1,b+1+n)-b-1;   // build(root[0],1,p);    for(int i=1;i<=n;i++){        root[i]=root[i-1];        int pos=lower_bound(b+1,b+1+p,a[i])-b;        update(root[i],pos,1,p);    }    while(m--){        int l,r,k;        l=read(),r=read(),k=read();        write(b[query(root[l-1],root[r],k,1,p)]);        putchar('\n');    }    return 0;}
         
        
       
      

 题2：https://www.luogu.org/problem/P3567

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;inline int read(){    int sum=0,x=1;    char ch=getchar();    while(ch<'0'||ch>'9'){        if(ch=='-')            x=0;        ch=getchar();    }    while(ch>='0'&&ch<='9')        sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar();    return x?sum:-sum;}inline void write(int x){    if(x<0)        putchar('-'),x=-x;    if(x>9)        write(x/10);    putchar(x%10+'0');}const int M=1e5+5;struct node{    int sum,L,R;}tree[M*40];int root[M],a[M],b[M],n,m,cnt;void build(int &now,int l,int r){    now=++cnt;    if(l==r)        return ;    int midd=(l+r)>>1;    build(tree[now].L,l,midd);    build(tree[now].R,midd+1,r);}void update(int &rt,int pos,int l,int r){    tree[++cnt]=tree[rt];    tree[cnt].sum++;    rt=cnt;    if(l==r)        return ;    int midd=(l+r)>>1;    if(pos<=midd)        update(tree[rt].L,pos,l,midd);    else        update(tree[rt].R,pos,midd+1,r);}int query(int i,int j,int len,int l,int r){    if(l==r)        return l;    int lsum=tree[tree[j].L].sum-tree[tree[i].L].sum;    int rsum=tree[tree[j].R].sum-tree[tree[i].R].sum;    int midd=(l+r)>>1;    if(lsum>len)            return query(tree[i].L,tree[j].L,len,l,midd);    else if(rsum>len)            return query(tree[i].R,tree[j].R,len,midd+1,r);    return 0;}int main(){    n=read(),m=read();    for(int i=1;i<=n;i++)        a[i]=read(),b[i]=a[i];    sort(b+1,b+1+n);    int p=unique(b+1,b+1+n)-b-1;   // build(root[0],1,p);    for(int i=1;i<=n;i++){        root[i]=root[i-1];        int pos=lower_bound(b+1,b+1+p,a[i])-b;        update(root[i],pos,1,p);    }    while(m--){        int l,r;        l=read(),r=read();        int len=(r-l+1)>>1;        write(b[query(root[l-1],root[r],len,1,p)]);        putchar('\n');    }    return 0;}
         
        
       
      

 可持续化数组（主席树实现）

题：

可持久化数组可以用可持久化线段树实现

 

然后实现的方法就是每次在对应的历史版本进行path-copy。

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define pb push_backinline int read(){    int sum=0,x=1;    char ch=getchar();    while(ch<'0'||ch>'9'){        if(ch=='-')            x=0;        ch=getchar();    }    while(ch>='0'&&ch<='9')        sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar();    return x?sum:-sum;}inline void write(int x){    if(x<0)        putchar('-'),x=-x;    if(x>9)        write(x/10);    putchar(x%10+'0');}const int M=1e6+6;struct node{    int val,L,R;}tree[M*20];int root[M],a[M],cnt;void build(int &now,int l,int r){    now=++cnt;    if(l==r){        tree[now].val=a[l];        return ;    }    int midd=(l+r)>>1;    build(tree[now].L,l,midd);    build(tree[now].R,midd+1,r);}void update(int &rt,int pre,int x,int val,int l,int r){    rt=++cnt;    tree[rt]=tree[pre];    if(l==r){        tree[rt].val=val;        return ;    }    int midd=(l+r)>>1;    if(x<=midd)        update(tree[rt].L,tree[pre].L,x,val,l,midd);    else        update(tree[rt].R,tree[pre].R,x,val,midd+1,r);}int query(int rt,int x,int l,int r){    if(l==r)        return tree[rt].val;   int midd=(l+r)>>1;    if(x<=midd)        return query(tree[rt].L,x,l,midd);    else        return query(tree[rt].R,x,midd+1,r);}int main(){    int n,m;    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)        scanf("%d",&a[i]);    build(root[0],1,n);  //  cout<
          
           <
          
         
        
       
      

 主席树+（二维前缀+二分）二合一题：https://www.luogu.org/problem/P2468

#include
      
       using namespace std;int n,m,q;int sum[210][210][1003],num[210][210][1003];int a[210][210];int getsum(int x1,int y1,int x2,int y2,int k){    return sum[x2][y2][k]-sum[x2][y1-1][k]-sum[x1-1][y2][k]+sum[x1-1][y1-1][k];}int getnum(int x1,int y1,int x2,int y2,int k){    return num[x2][y2][k]-num[x2][y1-1][k]-num[x1-1][y2][k]+num[x1-1][y1-1][k];}void solve2(){    //预处理    int maxx=0;    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)            scanf("%d",&a[i][j]),maxx=max(maxx,a[i][j]);    //cout<
       
        <
        
         =k){                    sum[i][j][k]=sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k]+a[i][j];                    num[i][j][k]=num[i-1][j][k]+num[i][j-1][k]-num[i-1][j-1][k]+1;                }                else{                    sum[i][j][k]=sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k];                    num[i][j][k]=num[i-1][j][k]+num[i][j-1][k]-num[i-1][j-1][k];                }            }    /*for(int i=1;i<=n;i++){    /    for(int j=1;j<=m;j++)            cout<
         
          <<" ";        cout<
          
           >1;            if(getsum(x1,y1,x2,y2,midd)>=h)                l=midd+1,ans=midd;            else                r=midd-1;        }        //我们二分的k值，有可能=k的数有很多，会多出来很多无用的k。无用的k的和就是sum(a,b,c,d,k)-h，用无用的和除以k即得到多出来的k的数量，减去就好了。         printf("%d\n",getnum(x1,y1,x2,y2,ans)-(getsum(x1,y1,x2,y2,ans)-h)/ans);//若有多余的就减去多余的     }}const int M=5e5+5;int root[M];struct node{    int L,R,sum,w;}tree[M<<5];int cnt;void update(int &now,int pos,int l,int r){    tree[++cnt]=tree[now];    tree[cnt].sum+=pos;    tree[cnt].w++;    now=cnt;    if(l==r)        return ;    int midd=(l+r)>>1;    if(pos<=midd)        update(tree[now].L,pos,l,midd);    else        update(tree[now].R,pos,midd+1,r);}int query(int i,int j,int l,int r,int k){    if(l==r)        return (k+l-1)/l;///到叶子节点，意味着此区间只含有数值为l的节点，多少个不清楚，所以向上取整个数     int midd=(l+r)>>1;    int w=tree[tree[j].R].sum-tree[tree[i].R].sum;    if(k<=w)        return query(tree[i].R,tree[j].R,midd+1,r,k);    else        return query(tree[i].L,tree[j].L,l,midd,k-w)+tree[tree[j].R].w-tree[tree[i].R].w;}void solve1(){    for(int i=1;i<=m;i++){        int x;        scanf("%d",&x);        root[i]=root[i-1];        update(root[i],x,1,1000);    }    while(q--){        int x1,y1,x2,y2,h;        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&h);        if(tree[root[y2]].sum-tree[root[y1-1]].sum