主席树
荣一鸣
2018-10-09 10:12:45
## PART 1 静态主席树
主席树，作为一种线段树的变种，在用做求区间第k小值是十分有用
那么再说主席树之前，我们先思考一下区间第k小值怎样求。首先，我们将所有的数进行离散化，然后，我们对于每一个[1,i]的区间进行建树，见得的树内部的节点拥有三个值，左孩子，右孩子，以及该节点包括的区间l，r中原序列编号小于等于i且大小大于等于l，小于等于r的个数
然后就是可以前缀和了。我们将询问区间的[l，r]分为[1,r]-[1,l-1],这可以看成前缀和，但是怎么前缀和呢？就是将线段树中同一个节点的值相减
举个栗子，某个节点表示[1,i]的区间中大小为[l,r]中的个数，另一个节点表示[1,j]的区间中大小为[l,r]的个数，则两个个数相减，得到的就是在[j+1,i]中，大小在[l,r]中的个数
那么，我们求第k小就是比它小的个数为k-1的数就行了，那么我们就可以写出查询程序
```cpp
int que(int i,int j,int k,int l,int r){
int d=tree[tree[i].lson].val-tree[tree[j].lson].val;//大小从l到mid的数量
if(l==r) return l;
int mid=(l+r)>>1;
if(k<=d) return que(tree[i].lson,tree[j].lson,k,l,mid);//如果数量大于查询的k
else return que(tree[i].rson,tree[j].rson,k-d,mid+1,r);//注意新的k要把之前小于它的d个数的数量减去
}
```
首先，我们求出的d值就是在j-1到i中大小为l到mid的数量
如果这个数量比我们的k要小，那么我们要求的数就比mid要大，那么就要在右孩子里找，但是在右孩子里找的时候找的大小要从k减小到k-d，因为你在查找[l,r]里的第k小就会变成[mid+1,r]的第k-d小，相当于把[l,mid]的数都减去了。
直到查询到l==r才行
那么，我们就把该题的查询做完了，但是想一想，如果真的对于每一个区间[1,i]都做一颗线段树的话会空间太大，那么我们怎么才能节省空间？
我们来看一下这两课线段树，区间[1,i]与[1,i+1]的线段树就只有新加进来的数i+1是需要更新的
比如说我们新插进来的数的大小小于mid，那么对于这两课线段树，只有[1,mid]中不一样，其他地方都是一样的，所以我们就在需要新加点的时候加点，其他地方就沿用之前的点，就可以省空间了
```cpp
void update(int u,int &rt,int l,int r){
tree[cnt++]=tree[rt];//新插入的点的位置
rt=cnt-1;//因为沿用的是地址，所以直接把上一层的左孩子或右孩子编号换掉了
tree[rt].val++;//值得变化
if(l==r) return;
int mid=(l+r)>>1;
if(u<=mid) update(u,tree[rt].lson,l,mid);//继续向下更新
else update(u,tree[rt].rson,mid+1,r);//向下更新
}
```
然后注意一点，我们每个数的根节点的编号也要记录，下面是更新的外面的函数
```cpp
for(int i=1;i<=n;i++)
root[i]=root[i-1],update(rank[i],root[i],1,n);
```
注意刚进来的时候的rt不是左孩子或右孩子，而是根节点编号
那么下面放上完整程序
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt=1,rank[200010],root[200010];
struct treepoint{
int lson,rson,val;
}tree[4000010];
struct node{
int id,vl;
bool operator < (const node b)const{
return vl<b.vl;
}
}p[200010];
void update(int u,int &rt,int l,int r){
tree[cnt++]=tree[rt];
rt=cnt-1;
tree[rt].val++;
if(l==r) return;
int mid=(l+r)>>1;
if(u<=mid) update(u,tree[rt].lson,l,mid);
else update(u,tree[rt].rson,mid+1,r);
}
int que(int i,int j,int k,int l,int r){
int d=tree[tree[i].lson].val-tree[tree[j].lson].val;
if(l==r) return l;
int mid=(l+r)>>1;
if(k<=d) return que(tree[i].lson,tree[j].lson,k,l,mid);
else return que(tree[i].rson,tree[j].rson,k-d,mid+1,r);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&p[i].vl),p[i].id=i;
sort(p+1,p+n+1);
for(int i=1;i<=n;i++) rank[p[i].id]=i;
for(int i=1;i<=n;i++) root[i]=root[i-1],update(rank[i],root[i],1,n);
for(int i=1;i<=m;i++){
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",p[que(root[r],root[l-1],k,1,n)].vl);
}
}
```
## PART 2 动态主席树
相比于静态主席树的只能查询不能修改的情况，我们选择用动态主席树来进行单点修改与区间查询
由于直接修改的话修改的大小就是树的个数乘上树的深度，即O(nlog(n))的时间复杂的，肯定爆炸
什么？单点修改区间查询？？。。。~~怎么感觉就是线段树呢？~~
然而我们仔细看发信区间第k小，由于k不同就必须套上主席树
我们把每个主席树放进来，这个单点修改区间查询就变成了区间修改单点查询(修改从修改点到n的所有主席树，查询单个主席树上的值)
emmmm，线段树套主席树？？？不太可能
由于线段树的将O(n)优化为O(log(n))靠的是lazy_tag而我们这里怎么lazy_tag呢？本人想不到，只能选择树状数组
那么我们考虑树状数组，树状数组的期间修改单点查询靠的是差分，那么我们就尝试把它套进主席树内
我们将每一个树状数组的点换成一颗主席树，可能这个比较抽象，我们可以将一棵树先看成一个点，然后如果你加进来一个点，它的位置是i，那么从i到n的所有主席树上都要加进这个点，那么我们就进行差分，在i处加上这个点，在n+1处减去这个点，由于n+1超过了数的范围，怎么都查不到~~（手动滑稽）~~，我们就不用管它了
#### 建树
那么我们就从i到n每次加上lowbit(i)为根的主席树上加入这个点（操作同树状数组）
然后我们的插入的点就从nlog(n)变为了log(n)^2
```
void modify(int &rtt,int l,int r,int pos,int val){
if(!rtt) rtt=++tot;
tree[rtt].val+=val;
if(l==r) return;
int mid=(l+r)>>1;
if(pos<=mid) modify(tree[rtt].lson,l,mid,pos,val);
else modify(tree[rtt].rson,mid+1,r,pos,val);
}
void prepare_modify(int x,int k,int val){
for(int i=x;i<=n;i+=i&-i) modify(rt[i],1,len,k,val);
}
```
主函数中的程序
```
for(int i=1;i<=n;i++) prepare_modify(i,rank[i],1);
```
#### 查询
然后我们看一看查询，同树状数组，我们的查询也要加起来，从i到0，每次减去lowbit(i)为根的主席树都要加起来，然后在做一般的主席树查询（可以理解为从把每一颗主席树差分为多颗主席树，现在要把它合起来，而树状数组的枚举就是把这颗主席树分到了那些树里）
我们就需要多一个数组来存都用到了那几个主席树
```
int query(int l,int r,int k){
if(l==r) return l;
int mid=(l+r)>>1,sum=0;
for(int i=1;i<=cnt[1];i++) sum+=tree[tree[tmp[1][i]].lson].val;
for(int i=1;i<=cnt[0];i++) sum-=tree[tree[tmp[0][i]].lson].val;
if(k<=sum){
for(int i=1;i<=cnt[1];i++) tmp[1][i]=tree[tmp[1][i]].lson;
for(int i=1;i<=cnt[0];i++) tmp[0][i]=tree[tmp[0][i]].lson;
return query(l,mid,k);
}
else{
for(int i=1;i<=cnt[1];i++) tmp[1][i]=tree[tmp[1][i]].rson;
for(int i=1;i<=cnt[0];i++) tmp[0][i]=tree[tmp[0][i]].rson;
return query(mid+1,r,k-sum);
}
}
int prepare_query(int l,int r,int k){
memset(tmp,0,sizeof(tmp));
cnt[0]=cnt[1]=0;
for(int i=l-1;i;i-=-i&i) tmp[0][++cnt[0]]=rt[i];
for(int i=r;i;i-=-i&i) tmp[1][++cnt[1]]=rt[i];//树状数组求出差分进了那几个主席树里
return query(1,len,k);
}
```
上面的tmp数组存了那些差分后的主席树需要查询，然后就求和相减，同时走向左子树或右子树时要将每一个主席树都走过去，也就是循环然后在走向下一层
主函数
```
printf("%d\n",o[prepare_query(q[i].l,q[i].r,q[i].k)].vl)
```
#### 修改
修改其实就是将每一个原来的点减去再把新的点加进来，而减去其实就是把插入一个参数改为负数就行了
直接放主函数，其他的上面有
```
prepare_modify(q[i].pos,rank[q[i].pos],-1);
rank[q[i].pos]=ppos[i];
prepare_modify(q[i].pos,ppos[i],1);
```
#### 离散化
其实我打的离散化比较烦，其实完全可以先全部离散化在二分查大小
那么我这里就放一下离散化程序，只可意会，不可言传，注意修改用的值也要加进来离散化
```
for(int i=1;i<=n;i++) scanf("%d",&o[++len].vl),o[len].id=i;
for(int i=1;i<=m;i++){
opt=getchar();
while(opt!='Q'&&opt!='C') opt=getchar();
q[i].b=(opt=='Q');
if(q[i].b) scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);
else scanf("%d%d",&q[i].pos,&q[i].t),o[++len].vl=q[i].t,o[len].id=0,o[len].pos=i;
}
sort(o+1,o+len+1);
o[0].vl=0;
o[0].nrank=0;//新的编号
for(int i=1;i<=len;i++){
o[i].nrank=o[i-1].nrank+1;
if(o[i].id) rank[o[i].id]=o[i].nrank;
//如果是原数组就将它的新编号放入rank，
//即rank[i]为原序列的第i个数的大小
else ppos[o[i].pos]=o[i].nrank;
//如果是修改的就放入ppos中
}
```
放一个总的程序
```
#include<bits/stdc++.h>
using namespace std;
const int MAX=100005;
struct treepoint{
int lson,rson,val;
}tree[MAX*400];
struct operation{
bool b;
int l,r,k,pos,t;
}q[MAX];
struct node{
int vl,id,nrank,pos;
bool operator < (const node b)const{
return vl<b.vl;
}
}o[MAX<<1];
int n,m,rank[MAX],rt[MAX],len,tot,tmp[2][20],cnt[2],ppos[MAX];
char opt;
void modify(int &rtt,int l,int r,int pos,int val){
if(!rtt) rtt=++tot;
tree[rtt].val+=val;
if(l==r) return;
int mid=(l+r)>>1;
if(pos<=mid) modify(tree[rtt].lson,l,mid,pos,val);
else modify(tree[rtt].rson,mid+1,r,pos,val);
}
void prepare_modify(int x,int k,int val){
for(int i=x;i<=n;i+=i&-i) modify(rt[i],1,len,k,val);
}
int query(int l,int r,int k){
if(l==r) return l;
int mid=(l+r)>>1,sum=0;
for(int i=1;i<=cnt[1];i++) sum+=tree[tree[tmp[1][i]].lson].val;
for(int i=1;i<=cnt[0];i++) sum-=tree[tree[tmp[0][i]].lson].val;
if(k<=sum){
for(int i=1;i<=cnt[1];i++) tmp[1][i]=tree[tmp[1][i]].lson;
for(int i=1;i<=cnt[0];i++) tmp[0][i]=tree[tmp[0][i]].lson;
return query(l,mid,k);
}
else{
for(int i=1;i<=cnt[1];i++) tmp[1][i]=tree[tmp[1][i]].rson;
for(int i=1;i<=cnt[0];i++) tmp[0][i]=tree[tmp[0][i]].rson;
return query(mid+1,r,k-sum);
}
}
int prepare_query(int l,int r,int k){
memset(tmp,0,sizeof(tmp));
cnt[0]=cnt[1]=0;
for(int i=l-1;i;i-=-i&i) tmp[0][++cnt[0]]=rt[i];
for(int i=r;i;i-=-i&i) tmp[1][++cnt[1]]=rt[i];
return query(1,len,k);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&o[++len].vl),o[len].id=i;
for(int i=1;i<=m;i++){
opt=getchar();
while(opt!='Q'&&opt!='C') opt=getchar();
q[i].b=(opt=='Q');
if(q[i].b) scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);
else scanf("%d%d",&q[i].pos,&q[i].t),o[++len].vl=q[i].t,o[len].id=0,o[len].pos=i;
}
sort(o+1,o+len+1);
o[0].vl=0;
o[0].nrank=0;
for(int i=1;i<=len;i++){
o[i].nrank=o[i-1].nrank+1;
if(o[i].id) rank[o[i].id]=o[i].nrank;
else ppos[o[i].pos]=o[i].nrank;
}
for(int i=1;i<=n;i++) prepare_modify(i,rank[i],1);
for(int i=1;i<=m;i++){
if(q[i].b) printf("%d\n",o[prepare_query(q[i].l,q[i].r,q[i].k)].vl);
else{
prepare_modify(q[i].pos,rank[q[i].pos],-1);
rank[q[i].pos]=ppos[i];
prepare_modify(q[i].pos,ppos[i],1);
}
}
}
```