[数据结构与算法]第K小数 (可持久化权值线段树)主席树经典题

第K小数 (可持久化权值线段树)主席树

题目Link

简述：题目给出N个整数，有M个询问每次询问区间L~R中第K小的数。

思路：本题给出的数组是个静态数组，所以给出的数全部都是确定的，我们可以通过建立可持久化线段树来使每一颗线段树维护所有的历史状态。因为数据范围很大而实际数量很少，所以我们需要使用离散化的操作，通过实际上出现的不同数的个数(离散去重后)，来$build$一个树的骨架并且刚开始没有元素，接下去$O(n)$扫描将每次新得到的数加入树，动态开点，更新树的结构，最多开辟$O(logn)$的空间。所以一开始的空间开辟除了基本的$N?4$还要开辟$NlogN$的空间用以动态开点。那么可持久化线段树也可以理解为一个弱小的士兵通过不断的获得装备从而变成强大的将军的一个过程。而本题所用到的即是这个伟大的将军在过去的两个阶段之间经历的事件，倘若我们把每次获得值的大小记为装备的好坏程度，那么我们需要做的就是查询在L~R期间，第K坏的装备是什么。

• 两篇不错的博客搭配使用更佳。
• $1:$acwing喵佬的题解
• $2:$躺着入门主席树的理解

非常好理解的$insert$过程：材料来于$Blog2$
假设主席树的上一个版本长这样（框外的数字代表该值域内有几个数，如[1,4] = 3表示有3个数在区间[1,4]内）：

现在我们要插入3，先新建一个当前版本的新节点，它指向上个版本根节点的左右子树，同时3在值域[1,4]内，其sum值+1：

然后我们康康它的左右子树值域范围，显然3在右子树的值域内，那我们就新建一个右子树节点，相应节点的sum值也+1：

递归更新直至到达叶子节点，至此一次更新完成：

• 详细代码加注释：

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N = 1e5+10;
int a[N];
int root[N];
vector<int>vec;//离散
struct Node{
    int l,r;//区间
    int cnt;//记录l~r中数值出现次数
}tr[N*4+N*17];//NlogN的动态开点
int idx;//记录当前点的id
int find(int x){//二分
    return lower_bound(vec.begin(),vec.end(),x)-vec.begin();
}
int build(int l,int r){
    int p=++idx;
    if(l==r)return p;//叶子
    int mid=l+r>>1;
    tr[p].l=build(l,mid),tr[p].r=build(mid+1,r);
    return p;
}
int insert(int p,int l,int r,int x){
    int q=++idx;//动态开点
    tr[q]=tr[p];
    if(l==r){
        tr[q].cnt++;
        return q;
    }
    int mid=l+r>>1;
    if(x<=mid)tr[q].l=insert(tr[p].l,l,mid,x);//只是单点操作
    else tr[q].r=insert(tr[p].r,mid+1,r,x);
    tr[q].cnt=tr[tr[q].l].cnt+tr[tr[q].r].cnt;//类似于pushup操作
    return q;
}
int query(int q,int p,int l,int r,int k){
    if(l==r)return r;
    int cnt=tr[tr[q].l].cnt-tr[tr[p].l].cnt;//类似于前缀和操作，将军的两个阶段之间，早的阶段及前面获得的值不算
    int mid=l+r>>1;
    if(k<=cnt)return query(tr[q].l,tr[p].l,l,mid,k);
    else return query(tr[q].r,tr[p].r,mid+1,r,k-cnt);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){cin>>a[i];vec.push_back(a[i]);}
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());//离散操作，留下有效数值。
    root[0]=build(0,vec.size()-1);//建立骨架进行成长，刚开始没有元素，空树
    for(int i=1;i<=n;i++){
        root[i]=insert(root[i-1],0,vec.size()-1,find(a[i]));
    }
    while(m--){
        int l,r,k;
        cin>>l>>r>>k;
        cout<<vec[query(root[r],root[l-1],0,vec.size()-1,k)]<<endl;
    }
    return 0;
}

与50位技术专家面对面

20年技术见证，附赠技术全景图