线段树进阶

• 线段树进阶
  • 权值线段树
  • 可持久化线段树与可持久化权值线段树 (主席树)
    • P3919 【模板】可持久化线段树 1（可持久化数组）
    • P3834 【模板】可持久化线段树 2

线段树进阶

权值线段树

权值线段树的思想就是让线段树存储的东西由下标变成了权值

也就是区间 \([l,r]\) 内实际上存储的是权值在 \([l,r]\) 范围内的数的个数

权值线段树有诸多用途，如我们可以查询 \([1,x)\) 来找到所有权值小于 \(x\) 的数的个数

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

可持久化线段树，俗称主席树，是一种非常强大的数据结构

假设每次操作得到的都是一个版本，通过可持久化，我们可以方便的查询每一个版本的内容

若是对于每次操作我们都建一棵线段树，这样很显然空间会爆炸

主席树就很好的解决了这一点

假设有 \(n\) 个点 \(m\) 次操作，主席树的核心思想就是：

由于每次修改的区间都对应线段树某一条从叶子节点到根的链，其余所有节点信息不变

因此我们新建一条链，让其所有节点的左右儿子以及父亲的信息与被修改的节点一样，并且让它们所维护的信息为修改后的信息

显然一条链最多 \(\log n\) 个点，空间复杂度就是 \(O((n+m)\log n)\)，时间复杂度是 \((n+m)\log n\) 的

注意：需要动态开点，不要吝啬空间

假如我们修改 \(1\sim8\) 这条链，树就会变成这样：

上几道例题

P3919 【模板】可持久化线段树 1（可持久化数组）

这个题要求在历史版本上修改和查询

直接上可持久化线段树

#include
using namespace std;

#define def register auto

const int N=2e6+5;

inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}

int n,m;
int a[N],rt[N];

namespace tree{
	struct node{
		int ls,rs;
		int v;
	}t[N*20];
	int cnt;
	inline void build(int &p,int l,int r){
		p=++cnt;
		if(l==r){
			t[p].v=a[l];
			return;
		}
		def mid=l+r>>1;
		build(t[p].ls,l,mid);
		build(t[p].rs,mid+1,r);
	}
	inline void insert(int &p,int pre,int l,int r,int x,int k){
		p=++cnt;
		t[p]=t[pre];
		if(l==r){
			t[p].v=k;
			return;
		}
		def mid=l+r>>1;
		if(x<=mid) insert(t[p].ls,t[pre].ls,l,mid,x,k);
		else insert(t[p].rs,t[pre].rs,mid+1,r,x,k);
	}
	inline int query(int p,int l,int r,int x){
		if(l==r) return t[p].v;
		int mid=l+r>>1;
		if(x<=mid) return query(t[p].ls,l,mid,x);
		return query(t[p].rs,mid+1,r,x);
	}
}

signed main(){
	n=read(),m=read();
	for(def i=1;i<=n;++i) a[i]=read();
	tree::build(rt[0],1,n);
	for(def i=1;i<=m;++i){
		def pre=read(),op=read();
		if(op==1){
			def x=read(),k=read();
			tree::insert(rt[i],rt[pre],1,n,x,k);
		}
		else{
			def x=read();
			printf("%d\n",tree::query(rt[pre],1,n,x));
			rt[i]=rt[pre];
		}
	}
}

P3834 【模板】可持久化线段树 2

典中典 \(\cdot\) 静态区间第 \(k\) 小

考虑用可持久化权值线段树完成此题

先离散化，然后我们对每一个前缀数列建立一个版本

查询区间 \([l,r]\) 的时候，我们直接用第 \(r\) 个版本的值减去第 \(l-1\) 个版本的值就可以得到 \([l,r]\)

具体细节见代码：

#include
using namespace std;
const int N=200005;
int n,m;
int a[N];
vector  p;
struct node{
    int l,r;
    int cnt;
}t[N*20];
int root[N],id;
inline int find(int x){
    return lower_bound(p.begin(),p.end(),x)-p.begin();
}
inline int build(int l,int r){
    int p=++id;
    if(l==r) return p;//返回节点编号
    int mid=l+r>>1;
    t[p].l=build(l,mid);
    t[p].r=build(mid+1,r);
    return p;
}
inline int insert(int now,int l,int r,int x){
    int p=++id;
    t[p]=t[now];//复制版本
    ++t[p].cnt;//x出现的次数+1
    if(l==r)
        return p;
    int mid=l+r>>1;
    if(x<=mid) t[p].l=insert(t[now].l,l,mid,x);
    else t[p].r=insert(t[now].r,mid+1,r,x);
    return p;
}
inline int query(int q,int p,int l,int r,int k){//l,r表示值域
    if(l==r) return l;
    int cnt=t[t[q].l].cnt-t[t[p].l].cnt;//版本[p,q]中1~l中的数出现的次数
    int mid=l+r>>1;
    if(k<=cnt) return query(t[q].l,t[p].l,l,mid,k);//排名第k的在[l,mid]范围内
    else return query(t[q].r,t[p].r,mid+1,r,k-cnt);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        p.push_back(a[i]);
    }
    sort(p.begin(),p.end());
    p.erase(unique(p.begin(),p.end()),p.end());
    root[0]=build(0,p.size()-1);//建立0版本的空树
    for(int i=1;i<=n;++i){
        int x=find(a[i]);
        root[i]=insert(root[i-1],0,p.size()-1,x);//对每一个前缀数列建立一个版本
    }
    while(m--){
        int l,r,k;
        cin>>l>>r>>k;
        cout<