主席树

作者: 陌路晨曦 | 来源:发表于2017-07-17 10:10 被阅读0次

主席树当然是很厉害的呀
【BZOJ 1901】 Zju2112 Dynamic Rankings
各种线段树https://wenku.baidu.com/view/a79e05ff941ea76e58fa046b.html
突然明白了主席树是什么鬼东西，网上博客看了一大堆看懵逼了。

http://blog.csdn.net/column/details/persistence-ds.html
离线的主席树【POJ 2104】K-th Number
非递归版本

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

const int MAXN=100000+100;
const int MAXM=MAXN*20;

int tot,n,m;
int da[MAXN],sDa[MAXN];
int leftChild[MAXM],rightChild[MAXM],wei[MAXM],chairTNode[MAXM*20];


/**********************************
*参数：待处理元素区间
*功能：建立一棵空线段树
*返回值：返回根节点下标
***********************************/
int Build(int left,int right)
{
    int id=tot++;
    wei[id]=0;
    if(left<right)
    {
        int mid=(left+right)>>1;
        leftChild[id]=Build(left,mid);
        rightChild[id]=Build(mid+1,right);
    }
    return id;
}


int Update(int root,int pos,int val)
{
    int l=1,r=m,mid,newRoot=tot++,retRoot=newRoot;
    wei[newRoot]=wei[root]+val;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(pos<=mid)
        {
            //确定节点孩子节点
            leftChild[newRoot]=tot++;
            rightChild[newRoot]=rightChild[root];

            //确定待跟新节点以及历史版本
            newRoot=leftChild[newRoot];
            root=leftChild[root];

            r=mid;
        }
        else 
        {
            rightChild[newRoot]=tot++;
            leftChild[newRoot]=leftChild[root];
            newRoot=rightChild[newRoot];
            root=rightChild[root];
            l=mid+1;
        }
        wei[newRoot]=wei[root]+val;
    }
    return retRoot;
}

int Query(int leftRoot,int rightRoot,int k)
{
    int  l=1,r=m,mid;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(wei[leftChild[leftRoot]]-wei[leftChild[rightRoot]]>=k)//第k小值在左子树
        {
            //确定查找新区间
            leftRoot=leftChild[leftRoot];
            rightRoot=leftChild[rightRoot];

            r=mid;
        }
        else 
        {
            k-=wei[leftChild[leftRoot]]-wei[leftChild[rightRoot]];
            leftRoot=rightChild[leftRoot];
            rightRoot=rightChild[rightRoot];
            l=mid+1;
        }
    }
    return l;
}

int main()
{
    int q,i;
    int ql,qr,k;
    while(scanf("%d%d",&n,&q)!=EOF)
    {
        m=0;
        tot=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&da[i]);
            sDa[i]=da[i];
        }
        sort(sDa+1,sDa+n+1);
        m=unique(sDa+1,sDa+1+n)-sDa-1;
        chairTNode[n+1]=Build(1,m);
        cout<<chairTNode[n+1]<<endl;
        //cout<<"**********"<<endl;
        printf("tot = %d\n",tot);
        for(i=n;i>=1;i--)  // 建n棵线段树 
        {
            int pos=lower_bound(sDa+1,sDa+1+m,da[i])-sDa;
            printf("pos = %d\n",pos);
            chairTNode[i]=Update(chairTNode[i+1],pos,1);
            printf("tot = %d\n",tot); 
        }
        while(q--)
        {
            scanf("%d%d%d",&ql,&qr,&k);
            printf("%d\n",sDa[Query(chairTNode[ql],chairTNode[qr+1],k)]);
        }
        printf("tot = %d\n",tot);
    }
    
    system("pause");
    return 0;
}

递归版本

#define lson l, m
#define rson m+1, r
const int N=1e5+5;
int L[N<<5], R[N<<5], sum[N<<5];
int tot;
int a[N], T[N], Hash[N];
int build(int l, int r)
{
    int rt=(++tot);
    sum[rt]=0;
    if(l<r)
    {
        int m=(l+r)>>1;
        L[rt]=build(lson);
        R[rt]=build(rson);
    }
    return rt;
}

int update(int pre, int l, int r, int x)
{
    int rt=(++tot);
    L[rt]=L[pre], R[rt]=R[pre], sum[rt]=sum[pre]+1;
    if(l<r)
    {
        int m=(l+r)>>1;
        if(x<=m)
            L[rt]=update(L[pre], lson, x);
        else
            R[rt]=update(R[pre], rson, x);
    }
    return rt;
}

int query(int u, int v, int l, int r, int k)
{
    if(l>=r)
        return l;
    int m=(l+r)>>1;
    int num=sum[L[v]]-sum[L[u]];
    if(num>=k)
        return query(L[u], L[v], lson, k);
    else
        return query(R[u], R[v], rson, k-num);
}

int main()
{
//    int t;
//    scanf("%d", &t);
//    while(t--)
//    {
        tot=0;
        int n, m;
        scanf("%d%d", &n, &m);
        for(int i=1; i<=n; i++)
        {
            scanf("%d", &a[i]);
            Hash[i]=a[i];
        }
        sort(Hash+1, Hash+n+1);
        int d=unique(Hash+1, Hash+n+1)-Hash-1;
        T[0]=build(1, d);
        for(int i=1; i<=n; i++)
        {
            int x=lower_bound(Hash+1, Hash+d+1, a[i])-Hash;
            T[i]=update(T[i-1], 1, d, x);
        }
        while(m--)
        {
            int l, r, k;
            scanf("%d%d%d", &l, &r, &k);
            int x=query(T[l-1], T[r], 1, d, k);
            printf("%d\n", Hash[x]);
        }
//    }
}