主席树 单点更新 区间第k大
程序员文章站
2024-03-02 22:03:34
...
话不多说直接写(好像咕了好久了)----2019.5.3
文章目录
主席数的概念
主席树又叫可持续性线段树,它可以保存区间各个修改时段的状态。它通过在原树上不断附加单链来实现logn复杂度的修改和记忆,子树间的联系不再是乘2或乘2加1而是通过直接存数组下标来实现保存(类似指针)。对不同时段的搜索也是依靠记录该时段根的下标来实现的。
讲一下主席树的搜索过程:
首先确定此次要搜索的是哪次的状态,确定是左子树还是右子树,沿着它记录的下标前进(下标可能走向任意方向),直到走到具体点为止。
luoguP3919
#include <iostream>
#include <cstdio>
using namespace std;
int n,m,cnt;//用内存池法建树,用cnt辅助建
const int maxn = 1e6+10;
struct node{
int lson,rson,num;//左子树,右子树的数组下标,维护的值
}infor[20*maxn];//空间需求大
int root[maxn];
void build_tree(int &p,int l,int r){
p=++cnt;//p为当前下标,持续增大
if(l==r){
scanf("%d",&infor[p].num);
return;
}
int mid=(l+r)/2;
build_tree(infor[p].lson,l,mid);//利用引用对左右子树进行赋值
build_tree(infor[p].rson,mid+1,r);
}
void update(int &p,int old,int tag,int l,int r,int val){
p=++cnt;//更新就建新树
infor[p]=infor[old];//集体复制
if(l==r){
infor[p].num=val;//找到定点,更新
return;
}
int mid=(l+r)/2;
if(tag<=mid){
update(infor[p].lson,infor[p].lson,tag,l,mid,val);//向目标方向更新,另一方向不变,后续检索时检索到原树上(形参里两个相同的值,第一个用于更新,第二个用于访问当前值,与指针的方式类似)
}
else{
update(infor[p].rson,infor[p].rson,tag,mid+1,r,val);
}
}
void query(int p,int tag,int l,int r){
if(l==r){
printf("%d\n",infor[p].num);
return;
}
int mid=(l+r)/2;
if(tag<=mid){
query(infor[p].lson,tag,l,mid);
}
else{
query(infor[p].rson,tag,mid+1,r);
}
}
int main(){
scanf("%d%d",&n,&m);
build_tree(root[0],1,n);
for(int i=1;i<=m;i++){
int ti,form;
scanf("%d%d",&ti,&form);
if(form==1){
int tag,val;
scanf("%d%d",&tag,&val);
update(root[i],root[ti],tag,1,n,val);//每次在指定的条件下做更新,用引用更新根的下标
}
else{
int tag;
scanf("%d",&tag);
query(root[ti],tag,1,n);
root[i]=root[ti];
}
}
return 0;
}
poj 区间第k大
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
const int maxn = 1e5+10;
struct node{
int lson,rson,sum;//sum维护在当前插入的所有值中,总大小排序在第l到第r之间的有多少个
}infor[40*maxn];
int n,m,cnt,inp[maxn],root[maxn];
vector<int> v;
int getpos(int a){//离散化找值
return lower_bound(v.begin(),v.end(),a)-v.begin()+1;
}
void update(int &p,int old,int tag,int l,int r){//建树
p=++cnt;
infor[p]=infor[old];
infor[p].sum++;
if(l==r){
return;
}
int mid=(l+r)/2;
if(mid>=tag){
update(infor[p].lson,infor[p].lson,tag,l,mid);
}
else{
update(infor[p].rson,infor[p].rson,tag,mid+1,r);
}
}
void query(int l,int r,int x,int y,int k){//x,y是在主席树上移动的方向,l,r是当前所查区间
if(l==r){
printf("%d\n",v[l-1]);
return;
}
int now=infor[infor[y].lson].sum-infor[infor[x].lson].sum;//出现的数目
int mid=(l+r)/2;
if(now>=k){//向左或右搜索
query(l,mid,infor[x].lson,infor[y].lson,k);//在当前左区间,总排序大小在第l到第mid的已经大于等于k了,所以第k大一定在子区间
}
else{
query(mid+1,r,infor[x].rson,infor[y].rson,k-now);//左子树的sum小于k,即在左子树找不到第k大,那么就应该在右子树找第k-左sum大的值
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&inp[i]);
v.push_back(inp[i]);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());//离散化
for(int i=1;i<=n;i++){
update(root[i],root[i-1],getpos(inp[i]),1,n);//每加一个值更新一次主席树,在原树的基础上把这个值加进去。与它相关的每一个区间值都加1,表示此区间大小范围内多了一个数
}
for(int i=0;i<m;i++){
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
query(1,n,root[l-1],root[r],k);//类似前缀和查法,在[l,r]之间查
}
return 0;
}
这个博客写的草率只是因为我懒,而且菜,毕竟看了一天才看懂这些问题。这个博客主要是为了自己以后查模板用,想具体学的话还是另找博客吧。(手动狗头)
下一篇: 全图中第K小路径/团问题(有向/无向)