区间最大值
传统解法是RMQ,但是题解都是RMQ,没有非常规解法,让我来一发主席树(可持续化线段树)的解法
在我的博客 食用会更香
主席树是解决动态查找序列上[l,r]区间中的第k小值的一个数据结构
核心思想:动态开点(后面会讲)
传统线段树都是值域线段树
其实意思就是每个节点都存的是序列上[l,r]的一个区间和,但是考虑我们需要动态处理区间的不是最值,故换一种线段树
主席树一般用的是权值线段树
就是把[l,r]改为[min(a),max(a)] a是序列A在[l,r]区间里的一个子序列,每个节点下都保存一个统计数字s,代表在当前权值域里,有多少个数字
array : 1 4 3 3
[1,4]
s = 4
[1,2] [3,4]
s = 1 s = 3
[1,1] [2,2] [3,3] [4,4]
s = 1 s = 0 s = 2 s = 1
(不会画图QWQ)
步入正题
我们转换思想,每一次开点都存储一个版本的权值线段树,但是这样会让空间复杂度直线上升为O(n^2),这是不能容忍的
但是我们再想
这是一颗树性结构,我们每一次加点都只会改变上下log n个点的数据,为什么我们就不能每一次都开一个log n的新点,将与这次更改无关的点直接开一条新边连接到新点呢?
不能像上一个那样形似了,我直接盗图
这是第一个版本在insert(4)后的结果
每一次insert都存储一个root[i+1],表示第i+1个版本的根节点
但是如何查询[l,r]区间内的第k小数呢
这时候就要运用我们前缀和的思想
[l,r]的信息 = [1,r]的信息 - [1,l-1]的信息
即 S[l,r] = S[1,r] - S[1,l-1]
离散化
这个其实没什么好讲的,就是预处理,详情见代码
大概意思是懂了吧,来,让我们步入总结
常规操作
1.插入insert(),动态开点
2.查询[l,r]区间内第k小值
3.离散化
时间复杂度 O(n log^2 n)
acwing 1270
C++ 代码
#include"bits/stdc++.h"
using namespace std;
const int N=200010;
#define inl inline
#define reg register
#define regi register int
#define PII pair<int,int>
//#define ll long long
#define lc(x) tr[x].l
#define rc(x) tr[x].r
inl int read(void)
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
struct node
{
int l,r,s;
}tr[N*20];
int root[N],idx;
int n,m,a[N];
vector<int> b;
inl void build(int &x,int l,int r)
{
x=++idx;
if(l==r) return;
int m=l+r>>1;
build(lc(x),l,m);
build(rc(x),m+1,r);
}
inl void insert(int x,int &y,int l,int r,int k)
{
y=++idx;tr[y]=tr[x];tr[y].s++;
if(l==r) return;
int m=l+r>>1;
if(k<=m) insert(lc(x),lc(y),l,m,k);
else insert(rc(x),rc(y),m+1,r,k);
}
inl int query(int x,int y,int l,int r,int k)
{
if(l==r) return l;
int m=l+r>>1;
int s=tr[lc(y)].s -tr[lc(x)].s;
if(k<=s) return query(lc(x),lc(y),l,m,k);
return query(rc(x),rc(y),m+1,r,k-s);
}
int b_n;
inl void Discretization_init()
{
sort(b.begin(),b.end());
b.erase(unique(b.begin(),b.end()),b.end());
b_n=b.size();
build(root[0],1,b_n);
for(regi i=1;i<=n;i++)
{
int id=lower_bound(b.begin(),b.end(),a[i])-b.begin()+1;
insert(root[i-1],root[i],1,b_n,id);
}
}
inl int get_k(int l,int r,int k)
{
return query(root[l-1],root[r],1,b_n,k)-1;
}
int main(void)
{
n=read(),m=read();
for(regi i=1;i<=n;i++)
{
a[i]=read();b.push_back(a[i]);
}
Discretization_init();
while(m--)
{
int l=read(),r=read();
printf("%d\n",b[get_k(l,r,r-l+1)]);
}
return 0;
}
luogu P3834
C++ 代码
#include"bits/stdc++.h"
using namespace std;
const int N=200010;
#define inl inline
#define reg register
#define regi register int
#define PII pair<int,int>
//#define ll long long
inl int read(void)
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
int a[N],n,m;
vector<int> num;
struct node
{
int l,r,s;//左右儿子下标,区间中一共有多少个数
}tr[N*20];
int root[N],idx;//root[i]为第i课线段树的节点编号
#define id(x) lower_bound(num.begin(),num.end(),x)-num.begin()
//id(x)为映射
int build(int l,int r)
{
int p=++idx;
if(l==r) return p;
int mid=l+r>>1;
tr[p].l=build(l,mid),tr[p].r=build(mid+1,r);
return p;//返回当前节点的编号
}
inl int insert(int p,int l,int r,int x)
{
int q=++idx;//创建新点q
tr[q]=tr[p];//复制旧点p
if(l==r)
{
tr[q].s++;
return q;
}
int mid=l+r>>1;
if(x<=mid) tr[q].l=insert(tr[p].l,l,mid,x);//x出现在左子树,修改左子树
else tr[q].r=insert(tr[p].r,mid+1,r,x);//x出现在右子树,修改右子树
tr[q].s=tr[tr[q].l].s+tr[tr[q].r].s;//统计
return q;//返回当前分配使用的新节点编号
}
inl int query(int q,int p,int l,int r,int k)//查询区间
{
if(l==r) return l;
int s=tr[tr[q].l].s-tr[tr[p].l].s;//线段树相减
int mid=l+r>>1;
if(k<=s) return query(tr[q].l,tr[p].l,l,mid,k);//左儿子数字大于或等于k时,说明第k小数在右子树
return query(tr[q].r,tr[p].r,mid+1,r,k-s);//否则在左子树
}
void init()
{
//离散化
sort(num.begin(),num.end());
num.erase(unique(num.begin(),num.end()),num.end());
root[0]=build(0,num.size()-1);
}
int main(void)
{
n=read(),m=read();
for(regi i=1;i<=n;i++)
{
a[i]=read();
num.push_back(a[i]);
}
init();
for(regi i=1;i<=n;i++) root[i]=insert(root[i-1],0,num.size()-1,id(a[i]));
while(m--)
{
int l=read(),r=read(),k=read();
printf("%d\n",num[query(root[r],root[l-1],0,num.size()-1,k)]);
}
return 0;
}
可持续化的思想都基本是这样的,包括可持续化平衡树,可持续化堆(注意是思想,比如可持续化堆有的时候就不能动态开点)