【学习笔记】主席树

发表于

主席树的时间复杂度：O(nlogn)
主席树的空间复杂度：O(nlogn)（开2logn比较好）
主席树的插入要用引用！

主席树的主体：

1
2
3
4
5
6
int rt[N],tot;
struct president_tree{
	int ls,rs,sz;
	LL sum;
	/* more */
}tr[N*150];//能开多大开多大

主席树是动态开点权值线段树，注意上下界的设置（注意inf的设置和0/1的设置）
因为主席树是不支持修改的，所以一般都是一开始就把树建好
插入：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline void update(int &t,int l,int r,int val)
{
	tr[++tot]=tr[t];
	++tr[tot].sz;
	tr[tot].sum+=val;//先产生一个新点
	t=tot;//再赋值
	if(l==r)	return;
	int mid=l+(r-l)/2;//可能会爆int
	if(val<=mid)	update(tr[t].ls,l,mid,val);
	else	update(tr[t].rs,mid+1,r,val);
}
for(int i=1;i<=n;++i){
	rt[i]=rt[i-1];
	update(rt[i],1,inf,a[i]);
}

询问函数可以有返回值，也可以没有，而使用一个全局变量记录答案
注意：查询的时候要用ls或者rs的差！！
询问：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
LL tmp;
inline void query(int t1,int t2,int l,int r,int num)
{
	if(!num)	return;
	if(tr[t2].sz-tr[t1].sz<=num){
		tmp+=tr[t2].sum-tr[t1].sum;
		return;
	}
	if(l==r){
		tmp+=1ll*num*l;
		return;
	}
	int mid=l+(r-l)/2,t=tr[tr[t2].rs].sz-tr[tr[t1].rs].sz;
	if(num<=t)	query(tr[t1].rs,tr[t2].rs,mid+1,r,num);
	else{
		tmp+=tr[tr[t2].rs].sum-tr[tr[t1].rs].sum;
		query(tr[t1].ls,tr[t2].ls,l,mid,num-t);
	}
}

清空主席树：

1
2
tot=0;
//rt[]和tr[]里的东西都会重新加