数据结构 可持久化线段树
前言
欸？明明是想学可持久化\(trie\)的，突然被拐到了可持久化线段树？
可持久化线段树（主席树）
要学可持久化线段树，线段树肯定是学过了的吧
相比线段树，可持久化线段树的优势在于可以存储历史版本。详情参照这道题：【模板】可持久化数组（可持久化线段树/平衡树）
我们把题干化简一下：
这里有一个数组，需要支持一些操作
快速查询任意版本时，任意位置上的数字
快速将某一数字更改，生成一个船新版本
这里就不进一步启发了，直接讲解思路：可持久化线段树
假设，我们有一个初始版本的数组需要维护，我们不妨建一颗线段树
这时，假设第三个位置上的数字发生了变动，产生了一个船新版本。怎么办？我们先为这个船新版本再建一颗线段树试试
这也不妨是个解法，但是弊端显而易见：空间复杂度爆表。由于线段树的时间复杂度很优秀，所以我们的矛盾集中于：空间不足
通过观察图可以一目了然地发现，虽然新建了一颗线段树，但事实上只是变更了一个点而已。主要信息，甚至于说绝大部分信息都没有发生改变。将发生改变的信息用红色特殊标记后发现，刚好形成了一条链。那么..
我们干脆就把没有没有改变的那部分连接到原来的线段树上，为发生改动的部分单独建一条链，就可以完美解决空间不足的问题
每次插一条链的复杂度是\(O(\log n)\)，所以总空间复杂度是\(O(4\times n + n\log n)\)，满足要求
tips：由于建图建的七零八碎，所以需要动态开点
这部分是初始化时，建一颗完整的线段树：
int build(int l,int r){
int now=++tot;
if(l==r){
node[now].val=init[l];
return now;
}
else{
int mid=(l+r)>>1;
node[now].lson=build(l,mid);
node[now].rson=build(mid+1,r);
node[now].val=node[node[now].lson].val+node[node[now].rson].val;
}
return now;
}
这是为每一次更改信息的时候，新添一条链：
void updata(int p,int pre,int l,int r,int pos,int delta){
node[p].val+=delta+node[pre].val;
node[p].lson=node[pre].lson;
node[p].rson=node[pre].rson;
if(l==r) return;
int mid=(l+r)>>1;
if(pos<=mid) node[p].lson=++tot,updata(tot,node[pre].lson,l,mid,pos,delta);
// 看这儿，可能会有启发
if(mid+1<=pos) node[p].rson=++tot,updata(tot,node[pre].rson,mid+1,r,pos,delta);
}
其余的操作和线段树完全一致，就不单独赘述了。完整代码如下
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX=3e7+5;
struct data{
int lson,rson,val;
}node[MAX];
int n,m,tot;
int init[MAX],root[MAX];
inline int read();
int qsum(int,int,int,int,int);
int build(int,int);
void copy(int,int);
void updata(int,int,int,int,int,int);
int main(){
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
#endif
n=read(); m=read();
for(int i=1;i<=n;++i) init[i]=read();
root[0]=build(1,n);
for(int k=1;k<=m;++k){
int v,type,loc,value,delta;
v=read(); type=read();
switch(type){
case 1:
loc=read(); value=read();
delta=value-qsum(root[v],1,n,loc,loc);
root[k]=++tot;
updata(tot,root[v],1,n,loc,delta);
break;
case 2:
loc=read();
printf("%d\n",qsum(root[v],1,n,loc,loc));
root[k]=++tot;
copy(root[v],tot);
break;
}
}
return 0;
}
inline int read(){
char tmp=getchar(); int sum=0; bool flag=false;
while(tmp<'0'||tmp>'9'){
if(tmp=='-') flag=true;
tmp=getchar();
}
while(tmp>='0'&&tmp<='9'){
sum=(sum<<1)+(sum<<3)+tmp-'0';
tmp=getchar();
}
return flag?-sum:sum;
}
int qsum(int p,int l,int r,int L,int R){
if(L<=l&&r<=R) return node[p].val;
int mid=(l+r)>>1,sum=0;
if(L<=mid) sum+=qsum(node[p].lson,l,mid,L,R);
if(mid+1<=R) sum+=qsum(node[p].rson,mid+1,r,L,R);
return sum;
}
int build(int l,int r){
int now=++tot;
if(l==r){
node[now].val=init[l];
return now;
}
else{
int mid=(l+r)>>1;
node[now].lson=build(l,mid);
node[now].rson=build(mid+1,r);
node[now].val=node[node[now].lson].val+node[node[now].rson].val;
}
return now;
}
void copy(int a,int b){
node[b].lson=node[a].lson;
node[b].rson=node[a].rson;
node[b].val=node[a].val;
}
void updata(int p,int pre,int l,int r,int pos,int delta){
node[p].val+=delta+node[pre].val;
node[p].lson=node[pre].lson;
node[p].rson=node[pre].rson;
if(l==r) return;
int mid=(l+r)>>1;
if(pos<=mid) node[p].lson=++tot,updata(tot,node[pre].lson,l,mid,pos,delta);
if(mid+1<=pos) node[p].rson=++tot,updata(tot,node[pre].rson,mid+1,r,pos,delta);
}
静态第\(K\)大
主席树的经典问题。可以检验主席树是否能正确打出来
引入概念：权值线段树
权值线段树
权值线段树的每一个节点相当于一个桶，存放的是：一个区间的数出现的次数
对于第\(i\)棵树的第\([m,n]\)的区间，表示的是对于原序列的\([1,i]\)，区间内的数字排名第\([m,n]\)的个数
假如我们用第\(b\)棵树的\([m,n]\)区间减去第\(a-1\)棵树的\([m,n]\)区间，得到的便是原序列区间\([a,b]\)中，排名在\([m,n]\)的个数。如此一来，我们就可以快速获得原序列区间\([a,b]\)的，关于数字大小排名的信息。
由于权值线段树的特点，左区间代表的数字总是比右区间代表的数字要小，假如左区间的数字超过了\(k\)，那么第\(k\)大数字一定产生在左区间；反之一定产生在右区间。随着线段树不断二分下去，最后第\(k\)大也就被二分地确定下来
二分过程：
int query(int a,int b,int l,int r,int k){
if(l==r) return num[rev[l]].num; //离散化前对应的数字
int x=node[node[b].lson].val-node[node[a].lson].val;
int mid=(l+r)>>1;
if(x>=k) return query(node[a].lson,node[b].lson,l,mid,k);
else return query(node[a].rson,node[b].rson,mid+1,r,k-x);
}
哦，数字范围大，个数少，记得离散化一下
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX=2e5+5,MAXT=6e6+6;
struct data{
int num,id;
}num[MAX];
struct tree{
int lson,rson,val;
}node[MAXT];
int n,m;
int seg[MAX],rev[MAX];
int tot,root[MAX];
inline int read();
bool cmpn(data a,data b) {return a.num<b.num;}
bool cmpi(data a,data b) {return a.id<b.id;}
int build(int,int);
void updata(int,int,int,int,int);
int query(int,int,int,int,int);
int qsum(int,int,int,int,int);
int main(){
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
#endif
n=read(); m=read();
for(int i=1;i<=n;++i) {num[i].id=i; num[i].num=read();}
sort(num+1,num+1+n,cmpn);
for(int i=1;i<=n;++i) seg[num[i].id]=i;
for(int i=1;i<=n;++i) rev[seg[i]]=i;
sort(num+1,num+1+n,cmpi);
root[0]=build(1,n);
for(int i=1;i<=n;++i) {root[i]=++tot,updata(tot,root[i-1],1,n,seg[i]);}
for(int i=1;i<=m;++i){
int l=read(),r=read(),k=read();
printf("%d\n",query(root[l-1],root[r],1,n,k));
}
return 0;
}
inline int read(){
char tmp=getchar(); int sum=0; bool flag=false;
while(tmp<'0'||tmp>'9'){
if(tmp=='-') flag=true;
tmp=getchar();
}
while(tmp>='0'&&tmp<='9'){
sum=(sum<<1)+(sum<<3)+tmp-'0';
tmp=getchar();
}
return flag?-sum:sum;
}
int build(int l,int r){
int now=++tot;
if(l==r) return now;
int mid=(l+r)>>1;
node[now].lson=build(l,mid);
node[now].rson=build(mid+1,r);
return now;
}
void updata(int p,int pre,int l,int r,int k){
node[p].val=node[pre].val+1;
node[p].lson=node[pre].lson;
node[p].rson=node[pre].rson;
if(l==r) return;
int mid=(l+r)>>1;
if(k<=mid) {node[p].lson=++tot,updata(node[p].lson,node[pre].lson,l,mid,k);}
if(mid+1<=k) {node[p].rson=++tot,updata(node[p].rson,node[pre].rson,mid+1,r,k);}
}
int query(int a,int b,int l,int r,int k){
if(l==r) return num[rev[l]].num;
int x=node[node[b].lson].val-node[node[a].lson].val;
int mid=(l+r)>>1;
if(x>=k) return query(node[a].lson,node[b].lson,l,mid,k);
else return query(node[a].rson,node[b].rson,mid+1,r,k-x);
}
int qsum(int p,int l,int r,int L,int R){
if(L<=l&&r<=R) return node[p].val;
int mid=(l+r)>>1,ans=0;
if(L<=mid) ans+=qsum(node[p].lson,l,mid,L,R);
if(mid+1<=R) ans+=qsum(node[p].rson,mid+1,r,L,R);
return ans;
}
动态第\(K\)大
题越出越丧心病狂，Dynamic Rankings
这道题在静态第\(K\)大的要求上，多支持了对数组的改动。这..（゜ー゜）
考虑一下，假如按照原来的思维该怎么解决。一旦题目要求更改第\(i\)个数字，那么我们就必须把第\([i,n]\)的线段树都修改一遍，复杂度\(O(n\log n)\)，好像不太优秀
想一想，原来的想法类似于前缀和。第\(i\)棵树实际上是前\(i\)个信息的前缀和。现在我们需要同时实现前缀和和单点修改.... 树状数组！
假如我们把每一棵线段树想象成树状数组中的一个变量，那么第\(i\)棵事实上存储的是区间\([i-lowbit(i)+1,i]\)的信息。
那么每一次维护更新，需要维护以下线段树：
for(int i=p;i<=n;i+=lowbit(i)) i;
每一次求前缀和，需要利用到以下线段树：
for(int i=p;i;i-=lowbit(i)) i;
而二分的时候，就要同时转移\(\log n\)棵线段树
int query(int l,int r,int k){
if(l==r) return l;
int suma=0,sumb=0,x,mid=(l+r)>>1;;
for(register int i=1;i<=transa[0];++i) suma+=node[node[transa[i]].lson].val;
for(register int i=1;i<=transb[0];++i) sumb+=node[node[transb[i]].lson].val;
x=sumb-suma;
if(x>=k){
for(register int i=1;i<=transa[0];++i) transa[i]=node[transa[i]].lson;
for(register int i=1;i<=transb[0];++i) transb[i]=node[transb[i]].lson;
return query(l,mid,k);
}
else{
for(register int i=1;i<=transa[0];++i) transa[i]=node[transa[i]].rson;
for(register int i=1;i<=transb[0];++i) transb[i]=node[transb[i]].rson;
return query(mid+1,r,k-x);
}
}
其余和静态第\(K\)大完全相同：
int query(int l,int r,int k){
if(l==r) return l;
int suma=0,sumb=0,x,mid=(l+r)>>1;;
for(register int i=1;i<=transa[0];++i) suma+=node[node[transa[i]].lson].val;
for(register int i=1;i<=transb[0];++i) sumb+=node[node[transb[i]].lson].val;
x=sumb-suma;
if(x>=k){
for(register int i=1;i<=transa[0];++i) transa[i]=node[transa[i]].lson;
for(register int i=1;i<=transb[0];++i) transb[i]=node[transb[i]].lson;
return query(l,mid,k);
}
else{
for(register int i=1;i<=transa[0];++i) transa[i]=node[transa[i]].rson;
for(register int i=1;i<=transb[0];++i) transb[i]=node[transb[i]].rson;
return query(mid+1,r,k-x);
}
}
例题
[CTSC2018]混合果汁,YSJ小朋友安利的CTSC题。据说用来检验主席树是否入门
这道题，首先需要看出来答案的单调性。即倘若大答案可行，那么小答案一定可行，因此二分答案。并且对美味度\(d\)降序排列。
二分之后，我们需要面对这样的问题：尽可能先贪心地买价格小的，后买价格大的
整理一下：需要支持对k的可持久化，需要维护最小值...
猛地想起来可持久化权值线段树，其实就是静态区间第\(K\)大。
那么，剩下的完全按照静态第\(K\)大来打：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX=6e7+6,TOP=1e5+5;
struct tree{
int lson,rson; ll val_l,val_c;
}node[MAX];
struct data{
int d,p; ll l;
}juice[TOP];
int n,m,tot;
int root[MAX];
inline int read();
inline ll readll();
bool cmpd(data a,data b) {return a.d>b.d;}
void build(int,int,int);
void updata(int,int,int,int,int);
bool judge(int,int,int,ll,ll);
int main(){
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
#endif
n=read(); m=read();
for(int i=1;i<=n;++i) juice[i].d=read(),juice[i].p=read(),juice[i].l=readll();
sort(juice+1,juice+1+n,cmpd);
root[0]=++tot; build(root[0],1,TOP);
for(int i=1;i<=n;++i) root[i]=++tot,updata(root[i-1],root[i],1,TOP,i);
for(int k=1;k<=m;++k){
ll g=readll(),L=readll();
int l=1,r=n; bool flag=false;
while(l<=r){
int mid=(l+r)>>1;
if(judge(root[mid],1,TOP,g,L)) r=mid-1,flag=true;
else l=mid+1;
}
printf("%d\n",flag?juice[l].d:-1);
}
return 0;
}
inline int read(){
char tmp=getchar(); int sum=0; bool flag=false;
while(tmp<'0'||tmp>'9'){
if(tmp=='-') flag=true;
tmp=getchar();
}
while(tmp>='0'&&tmp<='9'){
sum=(sum<<1)+(sum<<3)+tmp-'0';
tmp=getchar();
}
return flag?-sum:sum;
}
inline ll readll(){
char tmp=getchar(); ll sum=0; bool flag=false;
while(tmp<'0'||tmp>'9'){
if(tmp=='-') flag=true;
tmp=getchar();
}
while(tmp>='0'&&tmp<='9'){
sum=(sum<<1)+(sum<<3)+tmp-'0';
tmp=getchar();
}
return flag?-sum:sum;
}
void build(int p,int l,int r){
if(l==r) return;
int mid=(l+r)>>1;
node[p].lson=++tot; build(node[p].lson,l,mid);
node[p].rson=++tot; build(node[p].rson,mid+1,r);
}
void updata(int a,int b,int l,int r,int k){
node[b].val_l=node[a].val_l+juice[k].l;
node[b].val_c=node[a].val_c+juice[k].l*juice[k].p;
node[b].lson=node[a].lson;
node[b].rson=node[a].rson;
if(l==r) return;
int mid=(l+r)>>1;
if(juice[k].p<=mid) node[b].lson=++tot,updata(node[a].lson,node[b].lson,l,mid,k);
if(mid+1<=juice[k].p) node[b].rson=++tot,updata(node[a].rson,node[b].rson,mid+1,r,k);
}
bool judge(int p,int l,int r,ll g,ll L){
if(l==r) return (node[p].val_l>=L&&L*l<=g)?true:false;
int mid=(l+r)>>1;
ll x=node[node[p].lson].val_c,y=node[node[p].lson].val_l;
if(g>=x){
if(y>=L) return true;
return judge(node[p].rson,mid+1,r,g-x,L-y);
}
else return judge(node[p].lson,l,mid,g,L);
}