可持久化线段树
枫林晚
2018-05-10 18:17:07
可持久化线段树，意思是可以查询历史记录的线段树。又叫主席树。我们可以通过记录不同的根节点，并在每一个更新到的节点处新建必要的节点。询问不同版本的主席树，只需要进入不同的根节点即可。
例题：
给定n,m,输入n个数组成的数列，有m个询问，每次询问l,r这个区间中，第k小的数的值。
分析：
这个题可以巧妙运用主席树来解题。
首先对数列进行离散化。
我们令线段树的每一个节点，都代表排名为[i,j]区间内数字出现的次数。
假如我们每加入一个数，就新建一棵线段树，这一刻线段树大部分信息与前一棵一致，只是新加入的一个数相关的位置的信息发生了改变。相当于第i棵线段树，都维护的是[1,i]前i个数的信息。
发现对于区间查询[l,r]来说，对于任意一个排名位置上的数，它在这个区间里出现的次数，就是第r棵线段树上出现的次数减去第l-1棵线段树上出现的次数。同理，我们也可以利用这个前缀和思想算出来当询问[l,r]时，某个排名区间[i,j]里，所有的数出现的总次数。（只需要让两个版本的线段树中的对应区间的sum值相减即可。）
这样我们将数列从1到n扫一遍，每一次都将a[i]对已经的离散化的值（即排名）的位置加上1，（常规线段树操作）但是每次新建一个版本的线段树会使时空复杂度爆炸。
然而我们发现，相邻两个版本的线段树之间记录的信息基本相差无几，重新复制一遍实在是浪费。
所以采用主席树操作，就是仅改变logn个点的情况下，新建一棵线段树。
具体的操作是：
1.常规add操作中，每新到一个旧节点，就新建一个同样的节点，lson，rson都不变，只是这个区间内维护的sum（数字出现的次数）要比之前多一个。
2.之后，再根据待加入点与mid的关系，更新新节点左二子或者右儿子。
形象的理解一下，就是在原始线段树上，从根节点开始，沿着加入这个数的路径上新建了一条线。好像贴了一层皮。
查询操作是：
1.同时处理访问两个版本的线段树，直接处理sum的差值x。
2.如果这个差值要大于等于k，则第k大的数一定在这个节点的左二子维护的位置里；反之，询问右儿子中第k-x大的数即可。
详见代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int cnt;
int n,m;
int id,root[N];
int a[N],b[N];
int li(int x)
{
int k=lower_bound(a+1,a+cnt+1,x)-a;
return k;
}
struct node{
int ls,rs;
int sum;
#define ls(x) t[x].ls
#define rs(x) t[x].rs
#define s(x) t[x].sum
}t[18*N];
void pushup(int x)
{
s(x)=s(rs(x))+s(ls(x));
}
void build(int x,int l,int r)
{
//cout<<" build "<<l<<" "<<r<<" "<<x<<endl;
if(l==r)
{
ls(x)=rs(x)=-1;
s(x)=0;
return;
}
int mid=(l+r)>>1;ls(x)=++id;rs(x)=++id;
build(ls(x),l,mid);
build(rs(x),mid+1,r);
}
int add(int x,int l,int r,int to)
{
//cout<<" add "<<l<<" "<<r<<" "<<x<<endl;
int now=++id;
ls(now)=ls(x),rs(now)=rs(x),s(now)=s(x)+1;
if(l<r)
{
int mid=(l+r)>>1;
if(to<=mid) ls(now)=add(ls(x),l,mid,to);
else rs(now)=add(rs(x),mid+1,r,to);
}
return now;
}
int query(int u,int v,int l,int r,int k)
{
//cout<<" query "<<l<<" "<<r<<" old: "<<u<<" new: "<<v<<endl;
if(l==r) return l;
int x=s(ls(v))-s(ls(u));
int mid=(l+r)>>1;
if(x<k) return query(rs(u),rs(v),mid+1,r,k-x);
else return query(ls(u),ls(v),l,mid,k);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
sort(a+1,a+n+1);
cnt=unique(a+1,a+n+1)-a-1;
build(++id,1,cnt);
root[0]=1;
for(int i=1;i<=n;i++)
{
root[i]=add(root[i-1],1,cnt,li(b[i]));
}
int l,r,z;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&l,&r,&z);
int p=query(root[l-1],root[r],1,cnt,z);
printf("%d\n",a[p]);
}
return 0;
}
```