可持久化线段树
别名:主席树
应用:用于查询指定的闭区间 \([l,r]\) 内的第 \(k\) 小值。
思想:通过新开节点,把被修改的那条链存下来,得到一个新的根,再与之前的主席树建立关系。
实现:动态开点,并保存每个节点的左右儿子编号。记录左右儿子,并保存插入每个数的时候的根节点就可以实现持久化了。
本质:与线段树差不多,只需要找到插入 \(r\) 时的根节点版本,然后用普通线段树就可以做了。还需要联系前缀和,以在区间查询上达到 \(O(1)\) 的复杂度。
代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,inf=1e9;
struct Node{int l,r,val;
}tr[N<<5];
int root[N],top;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;
}
void build(int &node,int l,int r,int k){if(!node) node=++top;tr[node].val++;if(l==r) return;int mid=(l+r)>>1;if(k<=mid) build(tr[node].l,l,mid,k);else build(tr[node].r,mid+1,r,k);
}
int query(int a,int b,int l,int r,int k){if(l==r) return l;int mid=(l+r)>>1;int t=tr[tr[b].l].val-tr[tr[a].l].val;if(k<=t) return query(tr[a].l,tr[b].l,l,mid,k);else return query(tr[a].r,tr[b].r,mid+1,r,k-t);
}
void merge(int &x,int y){if(!x||!y){x+=y;return;}tr[x].val+=tr[y].val;merge(tr[x].l,tr[y].l);merge(tr[x].r,tr[y].r);
}
int main(){int n,m,l,r,k;n=read(),m=read();for(int i=1;i<=n;i++){k=read();build(root[i],-inf,inf,k);}for(int i=2;i<=n;i++) merge(root[i],root[i-1]);while(m--){l=read(),r=read(),k=read();printf("%d\n",query(root[l-1],root[r],-inf,inf,k));}return 0;
}
例题:P3919 【模板】可持久化线段树 1(可持久化数组),P3834 【模板】可持久化线段树 2