「学习笔记」可持久化线段树
InfiniteRobin · · 算法·理论
权值线段树 & 可持久化线段树
Part 1:权值线段树
在了解可持久化线段树前,必须了解权值线段树。
权值线段树是一种十分简单的线段树,对于对应区间
利用权值线段树,我们可以根据每一个节点的大小,不断向下查找,就可以找到任意排名的数了。
Part 2:可持久化线段树
可持久化线段树可以解决这样的问题:
给定
n 个整数构成的序列a ,将对于指定的闭区间[l,r] 查询其区间内的第k 小值。数据范围:
1 \le n,m \le 2×10^5 ,0 \le a_i \le 10^9 。
这个题目与前文提到的权值线段树的功能有几个区别:
- 需要保存
n 个不同的版本,实现可持久化。 - 需要处理任意范围的区间,而不是单纯的
[1,r] 。
一个个解决这些问题。
问题 1 :实现可持久化
我们需要存储
我们注意到,根据线段树的特点,我们每次新添加一个节点,从树根到叶子节点,只会经过
因此,我们在插入一个新的数值时,不需要全部重开,只需要新增
下图
具体来说,就是从前一个版本的根节点出发,并且每次新开一个节点作为新的节点。
首先,该新节点先继承前一个版本的对应节点(这里的对应代表记录相同的值域范围,例如上图中的节点
然后,对于查找,我们可以记录下每个版本的根节点编号,这样每次从对应编号的节点往下查找即可。
这样,我们就顺利解决了可持久化以及空间的问题。
Tips:显然,实现可持久化线段树需要动态开点。在本题的数据范围下,大约需要
问题 2 :在指定区间内进行查找
前置知识:前缀和思想。
很显然,我们可以在任意
目前,我们可以求解
显然,我们也可以处理
于是我们可以利用前缀和的思想将其联系在一起。
具体地说,我们现在要查找
不妨设这两个对应的节点分别是
根据定义,节点
同理,节点
那么到这里就很清晰了,区间
之后的操作就和普通的权值线段树的操作相同了:若
至此,我们就基本实现了可持久化线段树啦!
其他的细节
- 数据肯定时要离散化的(
那不然呢),离散化前需要去重。 - 注意内存。
- 注意那些有的没的。
Part 3:例题
模板
首先是板子。
- P3834 【模板】可持久化线段树 2
- SP3946 MKTHNUM - K-th Number
- P1533 可怜的狗狗
三道题,同一份代码(数据范围还是要注意下的)!
Code #1~3
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
// 去重后的长度
int n,m,idx,len;
//一个是原数组,另一个是去重 + 排序后的
int a[N],b[N];
int ls[N<<5],rs[N<<5],sum[N<<5],ver[N<<5];
int find(int x){ //离散找排名
return lower_bound(b+1,b+1+len,x)-b;
}
//建树
int build(int l,int r){
int now=++idx; //新开一个节点
if(l==r) return now;
int mid=(l+r)>>1;
ls[now]=build(l,mid);
rs[now]=build(mid+1,r);
return now;
}
//插入一个新数值
int insert(int l,int r,int pre,int k){
int now=++idx;
//先继承对应的节点的左右孩子,更新大小
ls[now]=ls[pre],rs[now]=rs[pre],sum[now]=sum[pre]+1;
if(l==r) return now;
int mid=(l+r)>>1;
if(k<=mid){
ls[now]=insert(l,mid,ls[now],k);
}
else{
rs[now]=insert(mid+1,r,rs[now],k);
}
return now;
}
// 当前节点 之前版本的对应节点
int query(int now,int pre,int l,int r,int k){
if(l==r) return l;
int mid=(l+r)>>1;
//前缀和思想
int x=sum[ls[now]]-sum[ls[pre]];
if(k<=x){
return query(ls[now],ls[pre],l,mid,k);
}
else{
return query(rs[now],rs[pre],mid+1,r,k-x);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i];
}
sort(b+1,b+1+n);
len=unique(b+1,b+1+n)-b-1;
ver[0]=build(1,len);
for(int i=1;i<=n;i++){
ver[i]=insert(1,len,ver[i-1],find(a[i]));
}
int l,r,k;
for(int i=1;i<=m;i++){
cin>>l>>r>>k;
cout<<b[query(ver[r],ver[l-1],1,len,k)]<<"\n";
}
return 0;
}
P3567 [POI2014] KUR-Couriers
题目大意:
给一个长度为
n 的正整数序列a 。共有m 组询问,每次询问一个区间[l,r] ,是否存在一个数在[l,r] 中出现的次数严格大于一半。如果存在,输出这个数,否则输出0 。数据范围:
1 \le n,m \le 5\times 10^5 ,1 \le a_i \le n 。
本题也可以用可持久化线段树解决。
修改一下查询函数即可通过此题。
具体来说,我们由原先的求排名变为求出现次数。
我们可以利用前缀和的思想(与原先无区别),求出区间内大于中间值和小于中间值的数据个数。然后分别判断是否大于总数的一半。如果是就继续在该子树中查找。否则直接返回
由于本题数据的特殊性,不离散化也是可以的。
Code #4
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
// 去重后的长度
int n,m,idx;
int a[N];
int ls[N<<5],rs[N<<5],sum[N<<5],ver[N<<5];
//建树
int build(int l,int r){
int now=++idx; //新开一个节点
if(l>=r) return now;
int mid=(l+r)>>1;
ls[now]=build(l,mid);
rs[now]=build(mid+1,r);
return now;
}
//插入一个新数值
int insert(int l,int r,int pre,int k){
int now=++idx;
//先继承对应的节点的左右孩子,更新大小
ls[now]=ls[pre],rs[now]=rs[pre],sum[now]=sum[pre]+1;
if(l>=r) return now;
int mid=(l+r)>>1;
if(k<=mid){
ls[now]=insert(l,mid,ls[now],k);
}
else{
rs[now]=insert(mid+1,r,rs[now],k);
}
return now;
}
// 当前节点 之前版本的对应节点
int query(int now,int pre,int l,int r,int k){
if(l>=r) return l;
int mid=(l+r)>>1;
//前缀和思想
int x=sum[ls[now]]-sum[ls[pre]],y=sum[rs[now]]-sum[rs[pre]];
//就这里改了一下
if(x>k){ //如果总数大于一半,就继续找
return query(ls[now],ls[pre],l,mid,k);
}
else if(y>k){
return query(rs[now],rs[pre],mid+1,r,k);
}
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
ver[0]=build(1,n);
for(int i=1;i<=n;i++){
ver[i]=insert(1,n,ver[i-1],a[i]);
}
int l,r;
for(int i=1;i<=m;i++){
cin>>l>>r;
cout<<query(ver[r],ver[l-1],1,n,(r-l+1)/2)<<"\n";
}
return 0;
}
P4587 [FJOI2016] 神秘数
题目大意不复述了。
我们可以先假设集合中的数都是排好序的,然后按顺序添加数字。
注意:以下所表示的区间均为值域区间。
设目前可以最大且满足题意的区间为
初始时,
注意到询问的答案就是在所有数都添加完后,
那么我们每次可以添加的数是多少呢?
首先,可添加的最小值肯定是
然后确定一下右边界。由于我们上面说过,在目前答案为
综上,我们可以加入的数的区间就是
之后,由于我们把
设我们加入的数的总和为
众所周知,线段树可以实现区间求和,同样地,我们可以将其可持久化,实现求区间和的操作。
Tips:
- 不用离散化。
- 按照权值划分节点。
Code #5
#include<bits/stdc++.h>
#define i_ak_ioi true
using namespace std;
const int N=1e5+5,M=1e9;
int n,m,idx,len;
int a[N],b[N];
int ls[N<<5],rs[N<<5],ver[N<<5];
long long sum[N<<5];
//插入一个新数值
int insert(int l,int r,int pre,long long k){
int now=++idx;
//先继承对应的节点的左右孩子,更新数值
ls[now]=ls[pre],rs[now]=rs[pre],sum[now]=sum[pre]+k;
if(l==r) return now;
int mid=(l+r)>>1;
if(k<=mid){
ls[now]=insert(l,mid,ls[now],k);
}
else{
rs[now]=insert(mid+1,r,rs[now],k);
}
return now;
}
// 当前节点 之前版本的对应节点 当前区间 目标区间
long long query(int now,int pre,int L,int R,int l,int r){
//与普通线段树操作大致相同(只不过记录的是权值)
if(l<=L&&R<=r) return sum[now]-sum[pre];
long long ans=0;
int mid=(L+R)>>1;
if(l<=mid) ans+=query(ls[now],ls[pre],L,mid,l,r);
if(r>=mid+1) ans+=query(rs[now],rs[pre],mid+1,R,l,r);
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
ver[i]=insert(1,M,ver[i-1],a[i]);
}
cin>>m;
int l,r;
for(int i=1;i<=m;i++){
cin>>l>>r;
//一个是当前最大值,一个是能表示的最大值
long long maxn=0,ans=0;
while(i_ak_ioi == true){
long long res=query(ver[r],ver[l-1],1,M,maxn+1,ans+1);
if(res){
maxn=ans+1;
ans+=res;
}
else break;
}
cout<<ans+1<<"\n";
}
return 0;
}
Ending
本文的思路来源于 OI-Wiki,但是进行了细化与改良,把不是很清楚的地方用自己的语言解释出来。
欢迎指出文中的不当之处!
注: