可持久化权值线段树(主席树)

前置知识

权值线段树

可持久化线段树

当我们要保存每一个版本的线段树的时候,最暴力的算法就是开n个版本的整个线段树,但是由于n可能到2e5,所以空间肯定不够。

于是我们考虑可以将一些不变的节点合并,就变成了这样:
图片摘自洛谷日报

这幅图中,带'的节点表示新增节点。很容易看出,它利用几个指针,很有效地利用了不需要更改的空间。

当我们访问每一个版本的时候,就从当前版本的区间的根节点作为当前节点找下去。由于没有子节点连向父节点,所以不存在向下递归时访问到另外版本的情况。

而容易看出i号节点的子节点不一定是i2和i2+1,所以我们需要开一个struct,里面存节点数值和其左右子节点的编号。(这也是动态开点线段树)

权值线段树

权值线段树保存的并不是i-j的区间的 和 or 最大最小值,而是数值从i到j的数字的个数。由于记录的数字可能很大,我们一般在建树前先离散化,可以将区间大小缩小至 节点数 。

代码

P3834 【模板】可持久化线段树 2(主席树)
由于本题需要记录l-r区间,所以可以采取前缀和的方式求出答案。

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int Maxn=1e7;
int a[200005],li[200005];
struct t{
    int ls,rs,sum;
}tree[Maxn];
int root[200005];
int tot=0;
int build(int l,int r){
    int now=++tot;
    if(l==r)return now;
    int mid=(l+r)/2;
    tree[now].ls=build(l,mid);
    tree[now].rs=build(mid+1,r);
    return now;
}
int modify(int now,int l,int r,int goal,int sum){
    int pos=++tot;//开点
    tree[pos]=tree[now];//先将之前的信息复制到新开节点,然后再更改。
    if(l==r){
        tree[pos].sum+=sum;
        return pos;
    }
    int mid=(l+r)>>1;
    if(goal<=mid){
        tree[pos].ls=modify(tree[now].ls,l,mid,goal,sum);
    }
    else if(goal>mid){
        tree[pos].rs=modify(tree[now].rs,mid+1,r,goal,sum);
    }
    tree[pos].sum=tree[tree[pos].ls].sum+tree[tree[pos].rs].sum;
    return pos;
}
int query(int pos1,int pos2,int l,int r,int k){//pos1,pos2双线一起走
    if(l==r)return l;
    int mid=(l+r)>>1;
    int lcnt=tree[tree[pos2].ls].sum-tree[tree[pos1].ls].sum;
    if(lcnt>=k)return query(tree[pos1].ls,tree[pos2].ls,l,mid,k);
    else return query(tree[pos1].rs,tree[pos2].rs,mid+1,r,k-lcnt);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        li[i]=a[i];//离散化一定要新开数组
    }
    sort(li+1,li+1+n);
    int ed=unique(li+1,li+1+n)-li;//ed记录当前数组末尾再往后的位置
    root[0]=build(1,ed-1); 
    for(int i=1;i<=n;i++){
        int sum=lower_bound(li+1,li+ed,a[i])-li;
        root[i]=modify(root[i-1],1,ed-1,sum,1);//modify应以ed-1作为最后的位置
    }
    int l,r,k;
    for(int i=1;i<=m;i++){
        cin>>l>>r>>k;
        cout<<li[query(root[l-1],root[r],1,ed-1,k)]<<endl;
    }
    return 0;
} 

本文链接:http://kaispace.com.cn/index.php/archives/667/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者

    nodeee
    nodeee  2020-08-01, 14:05

    发现可持久化trie还没补QAQ