wy's Blog

昨天，机房金牌爷Gwy orz...教了机房群众关于主席树的内容。。。

wy在此膜拜金牌爷and写一份日志。。。

先提一下权值线段树。。。

权值线段树即把普通线段树中节点的位置和值交换。。。

也就是说权值线段树的节点维护的是权值区间。。。

下面说主席树。。。

金牌爷称 主席树即权值线段树的前缀和。。。

So?

我们用权值线段树解决整体k大数一类的问题，

主席树则可以解决区间k大数一类的问题。。。

先是建树，

每次在原有基础上加入一个数，

对于有更新的区间，我们拷贝原来的区间，然后再更新新区间

对于没有更新的区间，我们将它直接指向原来的区间(即共用一个节点)

这样，每次加数即是加入一条链，复杂度为log m,其中m为数的范围。。。

所以建树的总复杂度为O(n log m)。。。

void Insert(const int &y,int &x,const int &l,const int &r,const int &p){
	P[x=++tot]=P[y];
	++P[x].sum;
	if (l==r) return;
	int mid=(l+r)/2;
	if (p<=mid) Insert(P[y].l,P[x].l,l,mid,p);
	else Insert(P[y].r,P[x].r,mid+1,r,p);
}

然后是询问，

对于询问区间l,r,我们可以用 第 r 颗权值线段树 - 第 l-1 颗权值线段树 

以询问区间k大数为例。。。

我们从root[l-1]和root[r]开始

如果二者的左子树之差tmp ≥ k ，我们同时访问左子树。。。

否则，同时访问右子树，将 k-=tmp;

访问到叶子节点时，叶子节点的权值即为答案。。。

void find(const int &y,const int &x,const int &l,const int &r,const int &c){
	if (l==r){
		Ans=l;
		return;
	}
	int tmp=P[P[x].l].sum-P[P[y].l].sum;
	int mid=(l+r)/2;
	if (tmp>=c) find(P[y].l,P[x].l,l,mid,c);
	else find(P[y].r,P[x].r,mid+1,r,c-tmp);
}

我们建n颗权值线段树，第x颗权值线段树维护的是 x-lowbit(x)+1 到 x 的位置的情况

那么在x位置加入一个数k,

即为在 第 x ， x+lowbit(x) ， (x+lowbit(x) ) +lowbit(x+lowbit(x) )... 颗权值线段树上 都加入数k。。。

该操作的时间复杂度为O(log^2 n),空间复杂度也为O(log^2 n)。。。

#include<cstdio>
#define MaxN 66666  
#define MaxT 233333
int N,M,tot;
int root[MaxN];
struct point{
	int l,r,sum;
	point(int x=0,int y=0,int s=0){
		l=x; r=y; sum=s;
	}
}P[MaxT];
void Insert(int &x,const int &l,const int &r,const int &p){
	if (!x) x=++tot;
	++P[x].sum;
	if (l==r) return;
	int mid=(l+r)/2;
	if (p<=mid) Insert(P[x].l,l,mid,p);
	else Insert(P[x].r,mid+1,r,p);
}
int lowbit(int x){
	return x & (-x);
}
void Add(int x,int s){
    for (;x<=N;x+=lowbit(x))
        Insert(root[x],1,M,s);
}

修改操作即先删去原数，再在原位置上插入新数。。。

#include<cstdio>
#define MaxN 66666  
#define MaxT 233333
int N,M,tot;
int A[MaxN];
int root[MaxN];
struct point{
	int l,r,sum;
	point(int x=0,int y=0,int s=0){
		l=x; r=y; sum=s;
	}
}P[MaxT];
void Insert(int &x,const int &l,const int &r,const int &p){
	if (!x) x=++tot;
	++P[x].sum;
	if (l==r) return;
	int mid=(l+r)/2;
	if (p<=mid) Insert(P[x].l,l,mid,p);
	else Insert(P[x].r,mid+1,r,p);
}
void Reduce(const int &x,const int &l,const int &r,const int &p){
	--P[x].sum;
	if (l==r) return;
	int mid=(l+r)/2;
	if (p<=mid) Reduce(P[x].l,l,mid,p);
	else Reduce(P[x].r,mid+1,r,p);
}
int lowbit(int x){
	return x & (-x);
}
void Add(int x,int s){
    for (;x<=N;x+=lowbit(x))
        Insert(root[x],1,M,s);
}
void Delete(int x,int s){
	for (;x<=N;x+=lowbit(x))
	    Reduce(root[x],1,M,s);
}
void Change(int i,int x){
	Delete(i,A[i]);
	Add(i,x);
	A[i]=x;
}

对于询问区间l,r

我们用两个队列记录 与l-1有关的树 and 与r有关的树。。。

还是以询问区间k大数为例。。。

我们每次遍历这些树的左子树

如果  与r有关树的左子树和 - 与l-1有关树的左子树和  tmp  ≥ k  ,

         我们就同时访问这些树的左子树。。。

否则，同时访问这些树的右子树，k-=tmp。。。

同主席树，访问到叶子节点时，叶子节点的权值即为答案。。。

询问操作的复杂度同为O(log^2 n)

#include<cstdio>
#define MaxN 66666  
#define MaxT 233333
int N,M,tot;
int A[MaxN];
int Que[2][MaxN];
int root[MaxN];
struct point{
	int l,r,sum;
	point(int x=0,int y=0,int s=0){
		l=x; r=y; sum=s;
	}
}P[MaxT];
void find(int x,int k){
	Que[k][0]=0;
	for (;x;x-=lowbit(x))
	    Que[k][++Que[k][0]]=root[x];
}
void Query(int l,int r,int c){
	find(l-1,0);
	find(r,1);
	int Ans;
	int L=1,R=M;
	for (;;){
		if (L==R) {
		   Ans=L;
		   break;	
		}
		int mid=L+R>>1;
		int tmp=0;
		for (int i=1;i<=Que[1][0];++i)
	        tmp+=P[P[Que[1][i]].l].sum;
	    for (int i=1;i<=Que[0][0];++i)
	        tmp-=P[P[Que[0][i]].l].sum;
		if (tmp>=c){
			R=mid;
			for (int i=1;i<=Que[1][0];++i)
			    Que[1][i]=P[Que[1][i]].l;
			for (int i=1;i<=Que[0][0];++i)
			    Que[0][i]=P[Que[0][i]].l;
	    }
	    else{
			L=mid+1;
			for (int i=1;i<=Que[1][0];++i)
			    Que[1][i]=P[Que[1][i]].r;
			for (int i=1;i<=Que[0][0];++i)
			    Que[0][i]=P[Que[0][i]].r;
			c-=tmp;
	    }
	}
}

ps:代码有点小丑，敬请见谅。。。

至此，关于主席树的日志写完了。。。

后附 金牌爷Gwy的推荐题目：BZOJ2223  BZOJ1901  BZOJ3932  BZOJ3483