K-th Number POJ - 2104 (静态主席树)

传送门

题解：本文参考博文：传送门

主席树又叫函数式线段树，就是多颗线段树的相互连接形成的一种数据结构，其时间复杂度和空间复杂度都为为 O(nlogn)

首先可以看下怎么求整个区间的第K大值问题传送门，这篇博文讲的非常好了

来简化一下整个区间的第K大问题：求整个区间的第K大值问题。我们可以用线段树解决，让线段树的第 i 个叶子节点表示原数组中排第 i 的有多少个，而其他节点表示排第L~R 的有多少个，其中L、R 就是它控制的范围[L,R] 。例如，给你一组数：1，2，2，2，4，4，8. 让你求第5 小的数，你发现排第 1~4 小的数分别有 1，3，2，1 个，很明显排第5小的数在前面红色的数字 2 表示的数中，也就是数字4。

了解了如何求解整个区间的第K大值问题求法后呢，就开始静态主席树的讲解了

来考虑求任意区间的第K大值，利用到了前缀和的知识，比如给你一组数让你求区间[L,R] 内的和，一个简单的方法就是求出前缀和 sum[i]=a[1]+a[2]+…+a[i] ，然后让sum[R]-sum[L-1] 就是结果。这里也是一样，假设有 n 个数，我们需要建立n 颗结构完全相同（即节点个数和位置等都相同，只是节点表示的值不同）的线段树，也就是对原数组的每前 i 个值都建立一颗类似于前缀和的线段树，我们让第i 颗线段树存储区间 [1, i ] 内的第 1~K 大值情况，其中K为原数组中不同数的个数。根据上一段落中的介绍，我们是可以实现的。如果要计算区间 [L,R] 的第K大值，只需要让第R颗线段树的节点减去第L-1颗线段树对应的节点，然后在新的线段树上查找即可。

前面说过了因为所有的线段树都是同构的，每个节点代表的意思相同，都是前 i 个数中排在第 L~R 的数的个数。第 i 和第 j-1 颗线段树一相减就表示在第 j-1 ~ i 个数中排在第 L~R 的数的个数。

一、建树

下面的图针对的是数据：1，4，2，3所建的树。

上图是初始化时的状况，这时候还没往树中插入任何元素。图中每个矩形块表示一个节点，其中间绿色的数字表示当前数形成的线段树中排第L~R 的数的个数，其中L、R是这个节点所能表示的范围 [L,R]。矩形的左右两端的数就是这个节点表示的范围L和R了。至于节点外的数字可以看作是节点的编号，从1开始，按照中根遍历的顺序编号。对于每个叶子节点下面的红色数字表示的是在原数组中排第几。第 i 个叶子节点自然是表示排第 i 了。

上图分别为插入第1个数和插入第2个数所形成的线段树。将上面两图的对应节点相减一下，就得到了只插入第 2 个数时候形成的线段树呢？这里再强调一点，线段树的第 i 个叶子节点保存的不是数的值，而是在原数组中排第 i 的数有多少个，而其他节点表示的是排第 L~R 的数有多少个，其中L、R 就是这个节点所能表示的范围 [L,R]。

二、更新

上面说到了，如果原数组有n 个节点的话需要建立n 个线段树，十分耗费空间。发现，第 i 个线段树是在第i-1 个线段树的基础上改变了一些值而来的。所以，可不可以共用那些没有改动的值呢？当然是可以的了。

 

如上图所示，插入第 1 个数形成的线段树和初始化时的线段树的改动的部分就是图中红线圈起来的部分。所以我们只需要在原线段树的基础上加上这些点即可，其他点共用即可。

如上图所示，红色的部分就是插入第 1 个数形成的线段树，它共用了前一个线段树的一部分。注意，这时候新节点的编号不是从1开始重新编号的。

如上图所示，蓝色的部分就是插入第 2 个数形成的线段树，它又共用了前一个线段树的一部分。

正是通过考虑到插入一个数的时候只会更改log(n) 个节点，也就是树高个节点，所以这需要添加这些节点即可，这样一来就实现了压缩空间的目的。

三、查询

就如上面提到过的，如果要查询区间 [L,R] 先要让第R 颗线段树减去第L 颗线段树，然后在得到的新树中查找，其实这个过程可以一边相减一边查找，因为你要查找一个第K 大数，它所查找经过的节点路径是一定的。例如要查找第K 大数，已经得到了相减后的新树，如果新树根节点的左子树中有num 个数，如果num>=k ，则说明要查找的数在左子树中，否则在右子树中，利用递归查找即可，当区间长度为 1 时就查找到了。

具体实现：

用L、R数组保存节点所能表示的范围 [L,R]，sum数组表示排第第L~R 的数的个数。tol表示节点的编号，如果编号相同，则L、R、sum表示同一个节点。当然这里也可以用一个结构体保存一下。

a数组保存原数组，hash数组保存排序后的数组，T数组保存插入每个元素后形成的线段树的根节点的编号。

如果原数组中有n 个不同的数，则我们建一个叶子节点有n 个的线段树就可以了。它们分别排第 1~n 。获取不同的数的个数可以用unique函数。查找当前数排第几可以用lower_bound函数。

总结一下：主席树就是对原数组的前 i 个数建一颗线段树保存前 i 个数的第 1~n 大值信息，其中 n 为原数组中不同数的个数。由于插入当前数时只改变了logn个节点的值，所以前一棵树可以重复利用，大大节省了空间。在查询时，利用前缀和的性质，区间 [L,R] 对应的第 R颗数减去第 L-1 棵树，得到这段区间内的第 1~n 大值信息，然后查找。如果左子树中的数的个数大于要查找的 K ，则结果在左子树中，否则在右子树中查找。

附上代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

const int MAXN=100010;

int tol;
int L[MAXN<<5],R[MAXN<<5],sum[MAXN<<5];
int a[MAXN],T[MAXN],Hash[MAXN];

int build(int l,int r)
{
    int mid,root=++tol;
    sum[root]=0;
    if(l<r){
        mid=(l+r)>>1;
        L[root]=build(l,mid);
        R[root]=build(mid+1,r);
    }
    return root;
}

int update(int pre,int l,int r,int pos)
{
    int mid,root=++tol;
    L[root]=L[pre];
    R[root]=R[pre];
    sum[root]=sum[pre]+1;
    if(l<r){
        mid=(l+r)>>1;
        if(pos<=mid){
            L[root]=update(L[pre],l,mid,pos);
        }else{
            R[root]=update(R[pre],mid+1,r,pos);
        }
    }
    return root;
}

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

int main()
{
    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;
    tol=1;
    T[0]=build(1,d);
    int pos;
    for(int i=1;i<=n;i++){
        pos=lower_bound(Hash+1,Hash+d+1,a[i])-Hash;
        T[i]=update(T[i-1],1,d,pos);
    }
    int l,r,k;
    while(m--){
        scanf("%d%d%d",&l,&r,&k);
        pos=query(T[l-1],T[r],1,d,k);
        printf("%d\n",Hash[pos]);
    }
    return 0;
}