【数据结构】可持久化线段树初步

但是我们需要查询 ([l,r]) ，于是使用可持久化线段树来处理：查询 ([l,r]) 的 (k) 小数，基于前缀和的思想，无非是要知道第 (l-1) 到 (r) 次插入操作元素个数的情况，那么我们作个差就行了：将第 (r) 个版本对应节点的 (cnt) 减去 (l-1) 版本对应节点的 (cnt) 就能够获取相应地元素个数情况了，剩下的操作就是权值线段树的基本操作，结束。

代码

#include<bits/stdc++.h>
using namespace std;

/*
习惯约定：
u代表结点（编号）
p代表先前版本的位置指针
q代表最新版本的位置指针
*/

const int N=1e5+5, M=1e4+5;
int n,m;
int a[N];
vector<int> nums; // 离散化
int root[N];

int find(int x){
	return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
}

struct node{
	int l,r; // 这里的 l,r 并非区间边界，而是指向左右儿子结点的编号的指针
	int cnt; // 结点键值，维护个数。
}tr[4*N+17*N]; // 初始开的点数+logN * N （各版本总规模）

int idx;
// 返回建立的点的编号，两个参数分别代表左右边界。
int build(int l,int r){
	int u=++idx;
	if(l==r) return u;
	int mid=l+r>>1;
	tr[u].l=build(l,mid), tr[u].r=build(mid+1,r);
	return u;
}

// 递归地插入
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); // 如果更新的位置是在左边，那么 tr[q].l 为新开点
	else tr[q].r=insert(tr[p].r,mid+1,r,x); // 否则 tr[q].r 为新开点
	tr[q].cnt=tr[tr[q].l].cnt+tr[tr[q].r].cnt; // pushup the cnt
	return q;
}

int query(int p,int q,int l,int r,int k){
	if(l==r) return r;
	int mid=l+r>>1;
	int cnt=tr[tr[q].l].cnt-tr[tr[p].l].cnt;
	if(cnt>=k) return query(tr[p].l,tr[q].l,l,mid,k);
	else return query(tr[p].r,tr[q].r,mid+1,r,k-cnt);
}

int main(){
	cin>>n>>m;
	
	for(int i=1;i<=n;i++)
		cin>>a[i], nums.push_back(a[i]);
		
	sort(nums.begin(),nums.end());
	nums.erase(unique(nums.begin(),nums.end()),nums.end());
	
	root[0]=build(0,nums.size()-1); // 第0个版本指的就是空的线段树。
	
	for(int i=1;i<=n;i++)
		root[i]=insert(root[i-1],0,nums.size()-1,find(a[i]));
	
	while(m--){
		int l,r,k; cin>>l>>r>>k;
		cout<<nums[query(root[l-1],root[r],0,nums.size()-1,k)]<<endl; // 打印原来的值
	}

	return 0;
}

【数据结构】可持久化线段树初步

目录

简介

原理

代码