首页 > 其他分享 >替罪羊树

替罪羊树

时间：2025-01-22 11:12:28浏览次数：1  
标签：rt return lc int siz 替罪羊 rc

替罪羊树是一种平衡二叉搜索树。且它不依赖旋转操作，而只是基于一种暴力重构的操作来保证平衡。在暴力重构下它有 \(O(logn)\) 级别的树高，和奇妙的复杂度，一般操作都是 \(O(logn)\) 的。（证明好像要用势能分析）

关于它为什么要叫替罪羊树？我有一个猜测，就是随着插入，它的平衡会被破坏，这时就找一个破坏平衡的“替罪羊”，把它重构，就能平衡了。（以上纯口胡

重构

具体来说，定义一个平衡因子 \(alpha\) ，当某个节点 \(x\) 的某棵子树 \(x.ch.size>x.size*alpha\) 时便将这棵以 \(x\) 为根的子树拍扁重构。

另外，由于我们每次采用惰性删除（即不删除这个点，只给siz--），已删除节点过多也影响效率。因此若未被删除的子树大小占总大小的比例低于 \(alpha\) ，也重构。

重构的目的是让该子树变得平衡。考虑如何操作。

  1. 将该树拍扁。中序遍历展开，存入数组中。

  2. 重新建树。每次取区间中点为根，递归两边为左右子树建树。

重构的本质是交换节点位置，因此编号等信息无需更改。所以插入多少个节点，替罪羊树的空间复杂度就是多少。

时间复杂度分析：这样重构一次的复杂度为 \(O(n)\) ，而只有插入达到 \(size*alpha\) 的节点数目才会重构，可以通过势能分析证明替罪羊树单次操作均摊时间复杂度为 \(O(logn)\) .

经典操作

插入：同普通二叉搜索树，只是在递归返回的时候判断该子树是否需要重构

删除：并非真正删除，只是给点打一个标记，在重构时才删掉。

rank和kth操作：类似线段树，就是根据查询的k和当前节点的关系，分别往左或右子树递归。

平衡因子的取值

\(alpha\) 的范围在 0.5~1 左右，主要就是平衡树的深度和重构次数。

亲身尝试：我的代码 \(alpha\) 取 0.75~0.8 时比较快。

[模板] 普通平衡树 
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const double alpha=0.8;
int n,cnt,rt,tot,tmp[maxn];
struct node{
	int val,lc,rc;
	int c,s;//c本数据出现次数，s以本节点为根的子树大小（每个节点计num次
	int siz,sd;//siz以本节点为根的子树大小，sd已删除节点不计的子树大小（都是每个节点计1次 
}t[maxn];
void pushup(int x){
	t[x].siz=t[t[x].lc].siz+t[t[x].rc].siz+1;
	t[x].s=t[t[x].lc].s+t[t[x].rc].s+t[x].c;
	t[x].sd=t[t[x].lc].sd+t[t[x].rc].sd+(t[x].c!=0);
}
bool canrb(int x){
	return t[x].c&&(alpha*t[x].siz<=1.0*max(t[t[x].lc].siz,t[t[x].rc].siz)||t[x].sd<=alpha*t[x].siz);
}
void pia(int x){
	if(!x) return ;
	pia(t[x].lc);
	if(t[x].c) tmp[++tot]=x;
	pia(t[x].rc);
}
void build(int &x,int l,int r){
	if(l>r) return x=0,void();
	int mid=(l+r)>>1;
	x=tmp[mid];
	build(t[x].lc,l,mid-1);
	build(t[x].rc,mid+1,r);
	pushup(x);
}
void rbuild(int &x){
	tot=0;
	pia(x);
	build(x,1,tot);
}
void ins(int &x,int v){
	if(x==0){
		x=++cnt;
		t[x].val=v,t[x].lc=t[x].rc=0;
		t[x].c=t[x].s=t[x].siz=t[x].sd=1;
		return ;
	}
	if(v==t[x].val) t[x].c++;
	else if(v<t[x].val) ins(t[x].lc,v);
	else ins(t[x].rc,v);
	pushup(x);
	if(canrb(x)) rbuild(x);
}
void del(int &x,int v){
	if(x==0) return ;
	if(v==t[x].val) t[x].c--;
	else if(v<t[x].val) del(t[x].lc,v);
	else del(t[x].rc,v);
	pushup(x);
	if(canrb(x)) rbuild(x);
}
int kth(int x,int k){
	if(k<=t[t[x].lc].s) return kth(t[x].lc,k);
	else if(k>t[t[x].lc].s+t[x].c) return kth(t[x].rc,k-t[t[x].lc].s-t[x].c);
	return t[x].val;
}
int rnk(int x,int v){//这里直接查排名了，记得+1 
	if(x==0) return 1;
	if(t[x].val==v) return t[t[x].lc].s+1;
	else if(t[x].val>v) return rnk(t[x].lc,v);
	else return t[t[x].lc].s+t[x].c+rnk(t[x].rc,v);
}
int qpre(int v){
	return kth(rt,rnk(rt,v)-1);
}
int qnxt(int v){
	return kth(rt,rnk(rt,v+1));
}
int main(){
	scanf("%d",&n);
	while(n--){
		int opt,x;
		scanf("%d%d",&opt,&x);
		if(opt==1) ins(rt,x);
		else if(opt==2) del(rt,x);
		else if(opt==3) printf("%d\n",rnk(rt,x));
		else if(opt==4) printf("%d\n",kth(rt,x));
		else if(opt==5) printf("%d\n",qpre(x));
		else printf("%d\n",qnxt(x));
	}
	return 0;
}

例题

[湖北省队互测2014] 没有人的算术

这题最奇怪的地方是比较值的大小是递归定义的。考虑生成一个类似这个递归的结构并给数对赋上值从而方便比较。想到用二叉搜索树类似结构。

考虑需要维护的：有序的数对，且要随时插入保证平衡。普通的平衡树，要么是旋转，不能保证值的大小关系（splay）；要么是节点父子关系随机，以及分裂合并次数过多（FHQ-treap），关键是难以直接给它赋一个有序的值。

因此想到重构式平衡树——替罪羊树。它能完全维护数列顺序。

单点修改区间查询用普通线段树就行，就是pushup比较的时候用替罪羊树维护过的赋值。

[bzoj4066] 简单题

这东西就是 K-D tree。注意到空间限制+强制在线，我们没有什么投机取巧的方法。

它其实是为了说 K-D tree 的替罪羊式重构（其实用二进制分组写是一样的）。且替罪羊式重构可能导致查询时间复杂度退化，一般不是有删点的操作还是不建议使用。

//简单个* 调死我了。。。
#include<bits/stdc++.h>
using namespace std;
const double alpha=0.75;
const int maxn=2e5+5;
int n,ans,cnt,px,py,qx,qy,tot,rt,a[maxn];
struct kd_tree{
	int lc,rc,val,sum,siz,mx[2],mn[2],v[2];
}t[maxn];
void pushup(int x){
	t[x].sum=t[t[x].lc].sum+t[t[x].rc].sum+t[x].val;
	t[x].siz=t[t[x].lc].siz+t[t[x].rc].siz+1;
	for(int i=0;i<2;i++){
		t[x].mn[i]=t[x].mx[i]=t[x].v[i];
		if(t[x].lc){
			t[x].mn[i]=min(t[x].mn[i],t[t[x].lc].mn[i]);
			t[x].mx[i]=max(t[x].mx[i],t[t[x].lc].mx[i]);
		}
		if(t[x].rc){
			t[x].mn[i]=min(t[x].mn[i],t[t[x].rc].mn[i]);
			t[x].mx[i]=max(t[x].mx[i],t[t[x].rc].mx[i]);
		}
	} 
}
bool canrb(int x){
	return t[x].siz*alpha<=1.0*max(t[t[x].lc].siz,t[t[x].rc].siz);
}
int build(int l,int r,int d){
	if(l>r) return 0; 
	int mid=(l+r)>>1;
	nth_element(a+l,a+mid,a+r+1,[d](int x,int y){
		return t[x].v[d]<t[y].v[d];
	});
	int x=a[mid];
	t[x].lc=build(l,mid-1,d^1);
	t[x].rc=build(mid+1,r,d^1);
	pushup(x); 
	return x;
}
void pia(int x){
	if(!x) return ;
	a[++tot]=x;
	pia(t[x].lc);
	pia(t[x].rc);
}
void rebuild(int &x,int d){
	tot=0;
	pia(x);
	x=build(1,tot,d); 
}
void add(int &x,int d){
	if(!x){
		x=++cnt,t[x].lc=t[x].rc=0;
		t[x].val=t[x].sum=qx,t[x].siz=1;
		t[x].mn[0]=t[x].mx[0]=t[x].v[0]=px;
		t[x].mn[1]=t[x].mx[1]=t[x].v[1]=py; 
		return ;
	}
	if(t[x].v[0]==px&&t[x].v[1]==py){
		t[x].val+=qx,t[x].sum+=qx;
		return ;
	}
	int chk=(d==0)?px:py;
	if(chk<=t[x].v[d]) add(t[x].lc,d^1);
	else add(t[x].rc,d^1);
	pushup(x);
	if(canrb(x)) rebuild(x,d);
}
int query(int x){
	if(!x||t[x].mx[0]<px||t[x].mn[0]>qx||t[x].mx[1]<py||t[x].mn[1]>qy) return 0;
	if(t[x].mn[0]>=px&&t[x].mn[1]>=py&&t[x].mx[0]<=qx&&t[x].mx[1]<=qy) return t[x].sum;
	return ((t[x].v[0]>=px&&t[x].v[1]>=py&&t[x].v[0]<=qx&&t[x].v[1]<=qy)?t[x].val:0)+query(t[x].lc)+query(t[x].rc);
}
int main(){
	scanf("%d",&n);
	while(1){
		int opt;
		scanf("%d",&opt);
		if(opt==1){
			scanf("%d%d%d",&px,&py,&qx);
			px^=ans,py^=ans,qx^=ans;
			add(rt,0);
		} 
		else if(opt==2){
			scanf("%d%d%d%d",&px,&py,&qx,&qy);
			px^=ans,py^=ans,qx^=ans,qy^=ans;
			printf("%d\n",ans=query(rt));
		}
		else break;
	}
	return 0;
}

[bzoj3217] ALOEXT

思路并不算很难想，注意到替罪羊树的树高大约是logn的。

那么不妨用替罪羊树维护删除和添加操作，用01trie求解最大异或和问题。因此使用替罪羊树套01tire。（这里其他平衡树，一会分裂一会旋转的，都不能保证这个套01trie的正确性和复杂度。）

时空复杂度都是 \(O(nlognlogV)\) 的，数组要开够。

但这题就是代码死长，死难写。边界条件一堆细节。也就调了八九个小时吧……（破了我代码长度和调题时间的记录）

致敬传奇数据结构。。 
//重构吧
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5,K=19,mod=1048576;
const double alpha=0.9;
int n,m,a[maxn],cnt,R,lst; 
struct trie{
	int son[maxn*150][2],siz[maxn*150],pol[maxn*150],top,tot,rt[maxn];
	int newnode(){
		return top?pol[top--]:++tot;
	}
	void del(int &x){
		if(!x) return ;
		pol[++top]=x;
		siz[x]=son[x][0]=son[x][1]=0;
		x=0;
	}
	void insert(int id,int v){
		if(!rt[id]) rt[id]=newnode();
		int p=rt[id];
		for(int i=K;i>=0;i--){
			int x=(v>>i)&1;
			siz[p]++;
			if(!son[p][x]) son[p][x]=newnode();
			p=son[p][x];
		}
		siz[p]++;
	}
	void Delt(int id,int v){
		int p=rt[id];
		for(int i=K;i>=0;i--){
			siz[p]--;
			int x=(v>>i)&1;
			int nxt=p;
			p=son[p][x];
			if(siz[son[nxt][x]]==1) son[nxt][x]=0;//注意这里的写法、、 
		}
		siz[p]--;
	}
	int query(int id,int v){
		int p=rt[id],ret=0;
//		printf("%d\n",siz[0]);
		for(int i=K;i>=0;i--){
			int x=(v>>i)&1;
			if(son[p][!x]){
				p=son[p][!x];
				ret|=(1<<i);
			} else p=son[p][x];
//			printf("%d %d %d\n",p,x,ret);
		}
		return ret;
	}
	void clear(int &x){
		if(!x) return ;
		clear(son[x][0]);
		clear(son[x][1]);
		del(x);
	}
}T;
struct goattree{
	int tot,tmp;
	struct node{
		int mx,cmx,v,c,siz,rs,lc,rc;
	}t[maxn];
	void pushup(int x){
		t[x].mx=max(t[t[x].lc].mx,t[t[x].rc].mx);
		if(t[t[x].lc].mx==t[x].mx) t[x].cmx=max(t[t[x].lc].cmx,t[t[x].rc].mx);
		else t[x].cmx=max(t[t[x].lc].mx,t[t[x].rc].cmx);
		if(t[x].c){
			if(t[x].v>t[x].mx) t[x].cmx=t[x].mx,t[x].mx=t[x].v;
			else if(t[x].v>t[x].cmx) t[x].cmx=t[x].v;
		}
		t[x].siz=t[t[x].lc].siz+t[t[x].rc].siz+1;
		t[x].rs=t[t[x].lc].rs+t[t[x].rc].rs+(t[x].c!=0);
	}
	int build(int l,int r){
		if(l>r) return 0;
		int mid=(l+r)>>1;
		int x=a[mid];
		for(int i=l;i<=r;i++) T.insert(x,t[a[i]].v);
		t[x].lc=build(l,mid-1);
		t[x].rc=build(mid+1,r);
		pushup(x);
		return x;
	}
	void pia(int x){
		if(!x) return ;
		pia(t[x].lc);
		if(t[x].c) a[++cnt]=x;
		pia(t[x].rc);
		T.clear(T.rt[x]);
	}
	void rebuild(int &x){
		if(t[x].siz*alpha<t[x].rs&&t[x].siz*alpha>1.0*max(t[t[x].lc].siz,t[t[x].rc].siz)) return ;
		cnt=0;
		pia(x);
		x=build(1,cnt);
	} 
	void insert(int &x,int k,int val){
		if(!x){
			x=++tot;
			t[x]={val,-1,val,1,1,1,0,0};
			T.insert(x,val);
			return ;
		}
		T.insert(x,val);
		if(k<=t[t[x].lc].rs+t[x].c) insert(t[x].lc,k,val);
		else insert(t[x].rc,k-t[t[x].lc].rs-t[x].c,val);
		pushup(x);
		rebuild(x); 
	}
	void Del(int &x,int k){
		if(k==t[t[x].lc].rs+t[x].c&&t[x].c) t[x].c--,tmp=t[x].v;
		else if(k<=t[t[x].lc].rs+t[x].c) Del(t[x].lc,k);
		else Del(t[x].rc,k-t[t[x].lc].rs-t[x].c);
		T.Delt(x,tmp);
		pushup(x);
		rebuild(x);
	} 
	pair<int,int> qcmx(int x,int l,int r){
		if(!x||r<1) return make_pair(-1,-1);
//		printf("check  %d %d %d %d %d %d\n",x,l,r,t[x].rs,t[x].mx,t[x].cmx);
		if(l<=1&&t[x].rs<=r) return make_pair(t[x].mx,t[x].cmx);
		int tt=t[t[x].lc].rs+t[x].c;
		if(l>tt) return qcmx(t[x].rc,l-tt,r-tt);
		else if(r<tt) return qcmx(t[x].lc,l,r);
		else{
//			printf("%d %d\n",x,t[x].c);
			pair<int,int> A=qcmx(t[x].lc,l,r),B=qcmx(t[x].rc,l-tt,r-tt);
			int mx=max(A.first,B.first),cmx;
			if(mx==A.first) cmx=max(A.second,B.first);
			else cmx=max(A.first,B.second);
//				printf("%d\n",t[x].c);
			if(t[x].c){
				if(t[x].v>mx) cmx=mx,mx=t[x].v;
				else if(t[x].v>cmx) cmx=t[x].v;
//				printf("%d %d\n",x,mx);
			}
//			printf("%d %d %d %d %d %d\n",A.first,A.second,B.first,B.second,mx,cmx);
			return make_pair(mx,cmx);
		}
	}
	int query(int x,int l,int r,int p){
		if(!x||r<1) return 0;
		if(l<=1&&t[x].rs<=r) return T.query(x,p);
		int tt=t[t[x].lc].rs+t[x].c;
		if(l>tt) return query(t[x].rc,l-tt,r-tt,p);
		else if(r<tt) return query(t[x].lc,l,r,p);//不能加等号！因为这个节点会有值！！ 
		else{
			int ret=max(query(t[x].lc,l,r,p),query(t[x].rc,l-tt,r-tt,p));
			if(t[x].c) ret=max(ret,t[x].v^p);
			return ret;
		}
	}
}G;
int main(){
	scanf("%d%d",&n,&m);
	G.tot=n;
	G.t[0]={-1,-1,-1,0,0,0,0,0};
	for(int i=1,x;i<=n;i++){
		scanf("%d",&G.t[i].v);
		a[i]=i;
		G.t[i].c=1;
	}
	R=G.build(1,n);
	while(m--){
		char ch; int x,y;
		scanf(" %c%d",&ch,&x);
		if(ch=='I'){
			scanf("%d",&y);
			x=(x+lst)%n+1,y=(y+lst)%mod;
			G.insert(R,x,y);
			n++;
//			printf("1 %d %d\n",x,y);
		} else if(ch=='D'){
			x=(x+lst)%n+1;
			G.Del(R,x);
			n--;
//			printf("2 %d\n",x);
		} else if(ch=='C'){
			scanf("%d",&y);
			x=(x+lst)%n+1,y=(y+lst)%mod;
			G.Del(R,x);
			G.insert(R,x,y);
//			printf("3 %d %d\n",x,y); 
		} else{
			scanf("%d",&y);
			x=(x+lst)%n+1,y=(y+lst)%n+1;
//			printf("%d\n",G.t[2].rc);
			int p=G.qcmx(R,x,y).second;
//			printf("4 %d %d %d\n",x,y,p);
			lst=G.query(R,x,y,p);
			printf("%d\n",lst);
		} 
	}
	return 0;
}

[Wc2014] 紫荆花之恋

坑了，不会点分树、、

替罪羊树在这题的应用就是，它比 FHQ-treap、Splay 等平衡树快（

标签：rt,return,lc,int,siz,替罪羊,rc
From： https://www.cnblogs.com/YYYmoon/p/18682930

相关文章

  • 替罪羊树
    1概念替罪羊树是一种平衡树，它维护平衡的方式不是旋转或者随机权值，而是最简单的暴力重构。当在插入和删除的时候发现某个节点子树失衡就暴力拍平重构，如此保证均摊复杂度\(O(\logn)\)。当然这种思想不止运用在平衡树中，还用于重构其它的数据结构。2基本操作2.1重构既然是替......
  • 优雅的暴力：替罪羊树
    前言本文无大错误不再更新，会更新在博客。默认读者会BST的基本操作。节点定义替罪羊树采用了懒惰删除的方法，不会立即删除某个点，而是在重构时不放进数组。structnode{intch[2],val;intsiz1,siz2,cnt,sum;//扣去懒惰删除的节点数量，没扣去懒惰删除......
  • 替罪羊树学习笔记
    替罪羊树学习笔记史！思想众所周知，替罪羊树是一种平衡二叉搜索树，其拥有虽然我不理解为什么，但是很牛的复杂度。其思想在于通过一个系数进行定期重构，使得维护所有信息的树是一棵接近平衡树的伪平衡树，那么他依然拥有\(O(\logn)\)级别的层高，因此对于跳转查询依旧具有优异的复杂度......
  • 【博客】替罪羊树
    替罪羊树前言暴力即优雅替罪羊树是一种依赖于暴力重构操作维持平衡的平衡树它利用了一个平衡因子\(α\)来维持平衡\(α\)通常设0.7当一棵子树不满足平衡因子的条件的时候我们就把这棵子树拍扁重建听起来就很暴力在别人嗷嗷乱转的时候直接一巴掌上去一打一个不吱声感......
  • 平衡树学习笔记（替罪羊）
    替罪羊应该是所有平衡树中最简单的了（但这东西是真的恶心），它的主要思想是在发现子树不平衡时把子树拍平重建。首先我们考虑什么时候我们认为这个子树是不平衡的。我们可以设置一个常量\(eps\)，当有一棵子树的大小超过了它父节点子树大小乘\(eps\)，那么我们就可以重建这棵子树了。......
  • 替罪羊树
    替罪羊树是维护BST平衡的一种方式。它的方式为如果一个子树不平衡了，就拆毁重建。重建的方法为先用中序遍历得到一个序列，然后以这个序列中间的元素为根，这样可以把序列分成左右两段。将这两段分别建树，就可以得到一个平衡的BST。但它的时间复杂度很高，不能通过平衡树的模板题。......
  • 替罪羊树的效率
    （来自算法导论十七章摊还分析思考题\(\bold{17-3}\)，「摊还加权平衡树」）想当年替罪羊树可能是我第一个学习的平衡树。。。但是很少有人说明它均摊\(O(\lgn)\)的效率是从......
  • 《别找替罪羊》豆瓣：8.3
    作者:美国亚宾泽协会出版社:江西人民出版社出品方:后浪副标题:如何跳出自欺欺人的思维盒子原作名:Leadership&Self-Deception:GettingOutof......
  • 替罪羊树学习笔记
    前言替罪羊树（ScapegoatTree,SGT）是由ArneAndersson提出的一种非旋转自平衡树，可以做到单次均摊\(O(\logn)\)的时间复杂度内实现平衡树的所有操作（时间复杂度基于势能......
  • 浅谈替罪羊树
    前言噫，好！我又来了这几天闲着没事翻桃片，发现好多人卡评测被封了，就看了看紫荆花，发现splay会被卡，就去学了替罪羊树（\(\text{ScapegoatTree}\)）。正文写在前面大家都知道......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99