差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:替罪羊树 [2020/06/23 10:08]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:替罪羊树 [2021/08/11 10:20] (当前版本)
jxm2001 [代码模板]
@@ 行 5: / 行 5: @@
 一种平衡树，思维简单，码量少，速度还行，而且没有旋转操作。
-===== 算法思想 ====
+===== 算法思想 =====
 首先替罪羊树的插入类似普通的二叉搜索树，删除操作就是打上删除标记。
@@ 行 15: / 行 15: @@
 重构方法为中序遍历子树，将没有打上删除标记的结点加入序列。得到一个有序序列，然后用类似线段树建树的方法重新建树。
-重构操作虽然单次复杂度为 $O(n)$，但可以证明均摊复杂度为 $O(\log n)$，证明方法自行百度。
+重构操作虽然单次复杂度为 $O(n)$，但可以用势函数方法证明均摊复杂度为 $O(\log n)$，具体证明方法自行百度。
 问题在于何时考虑重构。
-考虑维护每个结点所在子树的未被删除的结点个数 $\text{cnt}$ 和结点总数 $\text{tot}$。
+考虑维护每个结点所在子树的未被删除的结点个数 $\text{sz}$ 和结点总数 $\text{tot}$。
-引入一个平衡因子 $\alpha$ 值，当 $\alpha\ast\text{cnt} \lt \max(\text{cnt}_{lson},\text{cnt}_{rson})$ 时考虑重构。
+引入一个平衡因子 $\alpha$ 值，当 $\alpha\ast\text{sz} \lt \max(\text{sz}_{lson},\text{sz}_{rson})$ 时考虑重构。
 $\alpha$ 过大将导致树的平衡度较差，查询效率低。 $\alpha$ 过小将导致树的重构次数过多，插入、删除效率低。
@@ 行 29: / 行 29: @@
 同时，如果一棵树上被删除的无效结点过多，也会影响查找效率，所以也需要重构。
-这里设置为当 $\alpha\ast\text{tot} \gt \text{cnt}$ 时考虑重构。
+这里设置 $\beta$ 值为 $0.4$，当 $\beta\ast\text{tot} \gt \text{sz}$ 时考虑重构。
 插入或删除结束后需要检查从根结点到插入结点的路径是否有结点需要重构，不能检查从插入结点到根结点的路径。
@@ 行 41: / 行 41: @@
 <hidden 查看代码>
 <code cpp>
-#include <cstdio>
-#include <algorithm>
-#include <cstring>
-#include <cctype>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=1e5+5;
-const double alpha=0.75;
+namespace scapegoat_tree{
-struct Node{
+	#define lch(k) node[node[k].lch]
-	int ch[2],v,cnt,tot;
+	#define rch(k) node[node[k].rch]
-	bool exist;
+	const double alpha=0.75,del_x=0.4,inf=1e9;
-	void build(int v){
+	struct Node{
-		this->v=v;
+		int lch,rch,v,sz,tot;
-		ch[0]=ch[1]=0;
+		bool exist;
-		cnt=tot=1;
+	}node[MAXN];
-		exist=true;
+	int node_cnt;
+	int new_node(int val){
+		int k=++node_cnt;
+		node[k].lch=node[k].rch=0;
+		node[k].v=val;
+		node[k].sz=node[k].tot=1;
+		node[k].exist=true;
+		return k;
 	}
-}node[MAXN];
+	int root,a[MAXN],n;
-int pool[MAXN],pos1,temp[MAXN],pos2,root;
+	bool isbad(int k){
-void Init(int n){
+		return alpha*node[k].sz<max(lch(k).sz,rch(k).sz);
-	for(int i=n;i>=1;i--)
-	pool[++pos1]=i;
-}
-bool isbad(int pos){return alpha*node[pos].cnt<max(node[node[pos].ch[0]].cnt,node[node[pos].ch[1]].cnt)?true:false;}
-bool isbad_2(int pos){return alpha*node[pos].tot>node[pos].cnt?true:false;}
-void dfs(int pos){
-	if(!pos)return;
-	dfs(node[pos].ch[0]);
-	if(node[pos].exist)temp[++pos2]=pos;
-	else pool[++pos1]=pos;
-	dfs(node[pos].ch[1]);
-}
-void build(int lef,int rig,int &pos){
-	if(lef>rig) return pos=0,void();
-	int mid=lef+rig>>1;
-	pos=temp[mid];
-	if(lef==rig){
-		node[pos].ch[0]=node[pos].ch[1]=0;
-		node[pos].cnt=node[pos].tot=1;
-		return;
 	}
-	build(lef,mid-1,node[pos].ch[0]);
+	bool isbad_2(int k){
-	build(mid+1,rig,node[pos].ch[1]);
+		return del_x*node[k].tot>node[k].sz;
-	node[pos].tot=node[pos].cnt=node[node[pos].ch[0]].cnt+node[node[pos].ch[1]].cnt+1;
-}
-void rebuild(int &pos){
-	pos2=0;
-	dfs(pos);
-	build(1,pos2,pos);
-}
-void check(int &pos,int x){
-	if(pos){
-		if(isbad(pos)||isbad_2(pos))
-		rebuild(pos);
-		else if(node[pos].v<x)
-		check(node[pos].ch[1],x);
-		else
-		check(node[pos].ch[0],x);
 	}
-}
+	void build(int &k,int lef,int rig){
-int rank(int x){
+		if(lef>rig) return k=0,void();
-	int pos=root,rk=1;
+		int mid=lef+rig>>1;
-	while(pos){
+		k=a[mid];
-		if(node[pos].v<x){
+		if(lef==rig){
-			rk+=node[node[pos].ch[0]].cnt+node[pos].exist;
+			node[k].lch=node[k].rch=0;
-			pos=node[pos].ch[1];
+			node[k].sz=node[k].tot=1;
+			return;
 		}
+		build(node[k].lch,lef,mid-1);
+		build(node[k].rch,mid+1,rig);
+		node[k].tot=node[k].sz=lch(k).sz+rch(k).sz+1;
+	}
+	void dfs(int k){
+		if(!k)return;
+		dfs(node[k].lch);
+		if(node[k].exist)a[++n]=k;
+		dfs(node[k].rch);
+	}
+	void rebuild(int &k){
+		n=0;
+		dfs(k);
+		build(k,1,n);
+	}
+	void check(int &k,int v){
+		if(k){
+			if(isbad(k)||isbad_2(k))
+			rebuild(k);
+			else if(v<node[k].v)
+			check(node[k].lch,v);
+			else
+			check(node[k].rch,v);
+		}
+	}
+	int rank(int v){// 返回小于 v 的个数+1
+		int k=root,rk=1;
+		while(k){
+			if(v<=node[k].v)
+			k=node[k].lch;
+			else{
+				rk+=lch(k).sz+node[k].exist;
+				k=node[k].rch;
+			}
+		}
+		return rk;
+	}
+	int kth(int rk){// 返回第 rk 小的数
+		int k=root;
+		while(k){
+			if(lch(k).sz+1==rk&&node[k].exist)return node[k].v;
+			if(lch(k).sz+node[k].exist>=rk)
+			k=node[k].lch;
+			else{
+				rk-=lch(k).sz+node[k].exist;
+				k=node[k].rch;
+			}
+		}
+		return inf;
+	}
+	void Insert(int &k,int v){
+		if(!k){
+			k=new_node(v);
+			return;
+		}
+		node[k].sz++;node[k].tot++;
+		if(v<node[k].v)
+		Insert(node[k].lch,v);
 		else
-		pos=node[pos].ch[0];
+		Insert(node[k].rch,v);
 	}
-	return rk;
+	void Insert(int v){
-}
+		Insert(root,v);
-int kth(int rk){
+		check(root,v);
-	int pos=root;
+	}
-	while(pos){
+	void Delate(int k,int rk){
-		if(node[node[pos].ch[0]].cnt+1==rk&&node[pos].exist)return node[pos].v;
+		node[k].sz--;
-		if(node[node[pos].ch[0]].cnt+node[pos].exist<rk){
+		if(lch(k).sz+1==rk&&node[k].exist){
-			rk-=node[node[pos].ch[0]].cnt+node[pos].exist;
+			node[k].exist=false;
-			pos=node[pos].ch[1];
+			return;
 		}
+		if(lch(k).sz+node[k].exist>=rk)
+		Delate(node[k].lch,rk);
 		else
-		pos=node[pos].ch[0];
+		Delate(node[k].rch,rk-lch(k).sz-node[k].exist);
 	}
-}
+	void Delate(int v){
-void Insert(int &pos,int x){
+		Delate(root,rank(v));
-	if(!pos){
+		check(root,v);
-		pos=pool[pos1--];
-		node[pos].build(x);
-		return;
 	}
-	node[pos].cnt++;node[pos].tot++;
+	int pre(int v){// 返回一个严格比 v 小的数
-	if(node[pos].v<x)Insert(node[pos].ch[1],x);
+		return kth(rank(v)-1);
-	else Insert(node[pos].ch[0],x);
-}
-void Insert(int x){
-	Insert(root,x);
-	check(root,x);
-}
-void Delate(int pos,int rk){
-	node[pos].cnt--;
-	if(node[node[pos].ch[0]].cnt+1==rk&&node[pos].exist){
-		node[pos].exist=false;
-		return;
 	}
-	if(node[node[pos].ch[0]].cnt+node[pos].exist<rk)Delate(node[pos].ch[1],rk-node[node[pos].ch[0]].cnt-node[pos].exist);
+	int suf(int v){// 返回一个严格比 v 大的数
-	else Delate(node[pos].ch[0],rk);
+		return kth(rank(v+1));
-}
+	}
-void Delate(int x){
+	#undef lch
-	Delate(root,rank(x));
+	#undef rch
-	check(root,x);
 }
 int main()
 {
-	int n=read_int(),opt,x,line=1;
+	int q=read_int(),opt,x;
-	Init(MAXN-1);
+	while(q--){
-	while(n--){
 		opt=read_int(),x=read_int();
 		switch(opt){
 			case 1:
-				Insert(x);
+				scapegoat_tree::Insert(x);
 				break;
 			case 2:
-				Delate(x);
+				scapegoat_tree::Delate(x);
 				break;
 			case 3:
-				enter(rank(x));
+				enter(scapegoat_tree::rank(x));
 				break;
 			case 4:
-				enter(kth(x));
+				enter(scapegoat_tree::kth(x));
 				break;
 			case 5:
-				enter(kth(rank(x)-1));
+				enter(scapegoat_tree::pre(x));
 				break;
 			case 6:
-				enter(kth(rank(x+1)));
+				enter(scapegoat_tree::suf(x));
 				break;
 		}

CVBB ACM Team

用户工具

站点工具

差别

页面工具