C++主席树求第k小得数模板程序详解

#include<bits/stdc++.h>
#define reint register int
using namespace std;
int n,m;
inline void read(int &a) {  //快读
    int x(0),y(1);
    char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-')y=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    a=x*y;
    return;
}
inline void write(int x) {  //快输
    if(x<0) {
        putchar('-');
        x=-x;
        write(x);
    } else {
        if(x>9) {
            write(x/10);
        }
        putchar(x%10+'0');
    }
}

int s[200005],p,root[200005],top,s_[200005],q,k;
struct nod {
    int l,r,val;
} tree[100000005];

int update(int node,int l,int r) {   //建1~n的树
    int new_node=++top;   //新建节点
    tree[new_node]=tree[node];  //新增节点，继承上一个节点
    tree[new_node].val++;  //因为是通过update增加一棵树，且每次增加都会有一个新的数进来，因此权值必+1
    if(l==r) {     //叶子节点
        return new_node;  //返回节点下标
    } else {
        int mid=(l+r)>>1;   //中间值
        if(p<=mid) {   //如果
            tree[new_node].l=update(tree[new_node].l,l,mid);  //看更新的节点在哪一颗子树，在左边就更新左子树
        } else {
            tree[new_node].r=update(tree[new_node].r,mid+1,r);  //否则右子树
        }
    }
    return new_node;  //返回新节点下标，用来给上一个节点记录子树下标
}


void build(int &node,int l,int r) {   //新建空树
    node=++top;   //新建节点下标
    tree[node].val=0;   //权值初始化
    if(l==r) {  //子节点
        return;   //返回
    }
    int mid=(l+r)>>1;   //中间值
    build(tree[node].l,l,mid);   //建左节点
    build(tree[node].r,mid+1,r);    //建右节点
}

int query(int lnode,int rnode,int l,int r,int k) {   //查询，解释在代码下面
    if(l==r) {
        return l;
    } else {
        int x=tree[tree[rnode].l].val-tree[tree[lnode].l].val;  
        int mid=(l+r)>>1;
        if(k<=x)
            return query(tree[lnode].l,tree[rnode].l,l,mid,k);
        else
            return query(tree[lnode].r,tree[rnode].r,mid+1,r,k-x);
    }
}

int main() {
    reint i,l,r;
    scanf("%d",&n);
    scanf("%d",&m);
    for(i=1; i<=n; ++i) {
        read(s[i]);
        s_[i]=s[i]; //复制，用来离散化
    }
    sort(s_+1,s_+n+1);   //离散化数组排序
    q=unique(s_+1,s_+n+1)-s_-1;   //s_数组去重
    build(root[0],1,q);  //用0根建议一颗空树
    for(i=1; i<=n; ++i) {
        p=lower_bound(s_+1,s_+1+q,s[i])-s_;  //此函数相当于在1~q的范围里找到第一个大于等于s[i]的数的下标（也就是s[i]应该在的位置），然后记录在p里
        root[i]=update(root[i-1],1,q);  //新增根节点，然后把s[i]加进数组
    }
    for(i=1; i<=m; ++i) {
        read(l);read(r);read(k);
        write(s_[query(root[l-1],root[r],1,q,k)]);  //query用来查找第k小的下标，然后用数组输出下标做代表的数
        putchar('\n');
    }
}

查询第k小的方法解释：

$^{^{图片来源}}$

假设我们要查1 ~ 3中第2小的值，我们要先确定查找的范围，也就是从第零个根（红色）到第三个根（绿色）的第2小，然后从做左到右按顺序查，先找到3的左节点和一的左节点，看这两个节点之间有几个在1 ~ 3之间（也就是用左子节点的值减去右子节点的值（因为节点存的就是数的个数）），显然减完后只有1，也就是这个区间只有一个数，然而我们要找第2小，因此要找右子节点，又因为我们是按数的顺序建的树，所以在左子节点那里面的一个数一定小于右子节点的所有数，所以我们只需要在右子节点里面找到第2-1小的数，就是整个区间第2小的数，后面的按这个顺序推下去，找到根节点就返回下标，就完成了查询操作。