主席树入门

主席树入门

总结

• 主席树 = 可持久化权值线段树;权值线段树是指线段树节点记录的是区间元素出现的频次，而可持久化则是通过记录历史版本来实现对历史情况的查询.可以用于静态的查询区间top k问题

核心操作

• 插入元素; 这意味着一个新的版本，需要生成沿查询路径的新的节点，这些节点的频次++
• 查询操作: 类似线段树的查询，不过是在不同的两个版本之间
• 注意点:

1. 可以在每次插入才生成新的节点，而不是一开始就生成一棵完整的树；这样做能节省空间
2. 堆式写法的线段树似乎难以适应新生成节点的情况，可以采用下面模板的写法；在需要的时候才进行开点
3. 空间开到(O(4*n+nlogn))应该没有问题，一次询问时间复杂度(O(logn))

模板题

模板

#include<bits/stdc++.h>
using namespace std;
#define db(x) cout<<"["<<#x<<"]="<<x<<endl
//静态序列 动态区间的第k小值

const int MAXN = 200005;
//2e5 nlogn = 20n 
int N,M;
struct Node {
    int lch, rch, val;//val记录频次,lch,rch 记录左右儿子
} tree[MAXN << 5];//32n
int tot = 0, rt[MAXN];//记录根的
vector<int> num;
int a[MAXN];

inline void insert(int &o, int l, int r, int x) {
    tree[++tot] = tree[o];
    o = tot;//新节点
    tree[o].val++;
    if(l==r) return ;//递归结束
    int mid = (l+r)>>1;
    if(x<=mid) insert(tree[o].lch,l,mid,x);
    else insert(tree[o].rch,mid+1,r,x);
    
}

inline int query(int o1, int o2, int l, int r, int k) {
    if(l==r) return l;
    int sz = tree[o2].val - tree[o1].val;
    int lsz = tree[tree[o2].lch].val - tree[tree[o1].lch].val;
    int mid = (l+r)>>1;
    if(lsz>=k) return query(tree[o1].lch,tree[o2].lch,l,mid,k);
    else return query(tree[o1].rch,tree[o2].rch,mid+1,r,k-lsz);
    
}
int main(){
    scanf("%d %d",&N,&M);
    for(int i=1;i<=N;i++){scanf("%d",a+i);num.push_back(a[i]);}
    sort(num.begin(),num.end());
    num.erase(unique(num.begin(),num.end()),num.end());
    /*
    for(auto t:num){
        cout<<t<<endl;
    }
    */
    int sz = num.size();
    for(int i=1;i<=N;i++){
        int t = lower_bound(num.begin(),num.end(),a[i])-num.begin()+1;
        //db(t);
        rt[i] = rt[i-1];
        //printf("insert %d
",t);
        insert(rt[i],1,sz,t);        
    }
    int l,r,k;
    for(int i=1;i<=M;i++){
        scanf("%d %d %d",&l,&r,&k);
        printf("%d
",num[query(rt[l-1],rt[r],1,sz,k)-1]);
    }
    return 0;

}