替罪羊树学习笔记

标签：sz cnt return seq int 替罪羊笔记学习 ls

前言

替罪羊树（Scapegoat Tree,SGT）是由 Arne Andersson 提出的一种非旋转自平衡树，可以做到单次均摊 \(O(\log n)\) 的时间复杂度内实现平衡树的所有操作（时间复杂度基于势能分析）。

替罪羊树的优点：

不需要进行左旋、右旋、单旋、双旋、伸展等基于旋转操作。减少了码量和思维量。
常数相对于常用的 Splay、FHQ Treap 较小（如 P6136，FHQ Treap 19.93 s，替罪羊树 16.05 s 相差近 \(4\) 秒）。

替罪羊树的缺点：

由于时间复杂度由势能分析保证，因此无法可持久化（不过似乎有人写了没被卡）
无法实现分裂、合并操作，也无法实现文艺平衡树。

前置姿势：二叉搜索树。（可以认为替罪羊树就是有平衡措施的二叉搜索树）

如果不会二叉搜索树建议看「学习笔记」浅析BST二叉搜索树 - do_while_true - 博客园 (cnblogs.com)。

约定

我们使用下面的结构体来存储节点：

struct node{
	int s,sz,sd,cnt,l,r,w;
	void init(int weight){
		w=weight;
		l=r=0;
		s=sz=sd=cnt=1;
	}
} t[10000005];

其中：

\(\texttt{s}\) 表示以当前节点为根的子树大小（不计重复元素，计删除了却保留下来的元素）（维护平衡使用）

\(\texttt{sz}\) 表示以当前节点为根的子树大小（计重复元素，计删除了却保留下来的元素）（基本操作使用）

\(\texttt{sd}\) 表示以当前节点为根的子树大小（不计重复元素，不计删除了却保留下来的元素）（维护平衡使用）

\(\texttt{cnt}\) 表示当前节点的元素个数。

\(\texttt{l,r}\) 分别表示当前节点的左、右子节点。

\(\texttt{w}\) 表示当前节点保存的值。

\(\texttt{init(weight)}\) 函数表示新建一个值为 \(\texttt{weight}\) 的节点的逻辑。

除此之外，我们还定义以下宏、变量：

#define ls (t[i].l)
#define rs (t[i].r)
int root,tot;
const double alpha=0.7;

\(\texttt{ls,rs}\) 的意义不必多说，\(\texttt{root}\) 是当前的根，\(\texttt{tot}\) 是当前已经有过多少个节点。

\(\alpha(\texttt{alpha})\) 表示的是平衡因子，在后面会有介绍。

信息上推

我们需要从子节点推出父节点的信息，就需要使用信息上推（Push Up）。

代码实现非常自然，就偷个懒，不讲了，代码如下：

void pushup(int i){
	t[i].s=t[ls].s+t[rs].s+1;
	t[i].sz=t[ls].sz+t[rs].sz+t[i].cnt;
	t[i].sd=t[ls].sd+t[rs].sd+(t[i].cnt>0);
}

维护平衡

总述

替罪羊树是基于”重构“（Rebuild）来实现平衡的。

所谓重构，不过是将子树打破直接暴力建出新树而已。同时还会不保留删除过的节点(\(\texttt{cnt}=0\))。

重构的契机

知道了什么是重构，接下来我们来想一想什么时候重构？

如果一个节点的子树大小 \(s_1\) 占到了这个节点的子树大小 \(s\) 的大部分，那么就需要重构这个节点。
如果一个节点的子树中未被删除的节点数 \(\texttt{sz}\) 占到了这个节点的子树大小 \(s\) 的小部分，那么就需要重构这个节点。

具体的大部分、小部分是多少呢？我们用 \(\alpha\)（平衡因子）来定义，可以像这样：

如果 \(\min\{s_{l},s_{r}\}\geq\alpha\cdot s\)，那么就需要重构这个节点。
如果 \(\texttt{sz}\leq\alpha\cdot s\)，那么就需要重构这个节点。

容易看出 \(\alpha\) 需要满足 \(\frac{1}{2}\leq\alpha\lt1\)。在实际应用中，一般取 \(0.7\) 或 \(0.8\)。

然后我们就可以写出一个判断函数：

bool need_rebuild(int i){
	if(t[i].cnt==0)return false;
	if(alpha*t[i].s<=(double)(max(t[ls].s,t[rs].s)))return true;
	if((double)t[i].sd<=alpha*t[i].s)return true;
	return false;
}

下面可能会将【需要重构】称之为【失衡】。

重构——平展

平展（Flatten）是重构中的前半部分，它指的是将一个子树按中序遍历展开。求中序遍历。

Flatten 在英文中还有精简的意思。在平展过程中我们也需要精简节点。就是将删完的节点(\(\texttt{cnt}=0\))从中序遍历中删除。

代码：

void flatten(int i,vector<int> &seq){
	if(!i)return;
	flatten(ls,seq);
	if(t[i].cnt)seq.push_back(i);
	flatten(rs,seq);
}

重构——建立

建立（Build）就是给出中序遍历，建出二叉搜索树。当然我们需要让建出来的数尽量平衡，只需要每一次选择区间 \([l,r]\) 的中部即可。具体细节如果不会，建议重新从普及组学起。

代码如下：

int build(int l,int r,const vector<int> &seq){
	if(l==r)return 0;
	int mid=(l+r)>>1;
	int i=seq[mid];
	ls=build(l,mid,seq);
	rs=build(mid+1,r,seq);
	pushup(i);
	return i;
}

重构实现

然后就成功实现重构部分了！贴个整体代码：

bool need_rebuild(int i){
	if(t[i].cnt==0)return false;
	if(alpha*t[i].s<=(double)(max(t[ls].s,t[rs].s)))return true;
	if((double)t[i].sd<=alpha*t[i].s)return true;
	return false;
}

namespace Rebuild{
	void flatten(int i,vector<int> &seq){
		if(!i)return;
		flatten(ls,seq);
		if(t[i].cnt)seq.push_back(i);
		flatten(rs,seq);
	}
	int build(int l,int r,const vector<int> &seq){
		if(l==r)return 0;
		int mid=(l+r)>>1;
		int i=seq[mid];
		ls=build(l,mid,seq);
		rs=build(mid+1,r,seq);
		pushup(i);
		return i;
	}
}

void rebuild(int &i){
	vector<int> seq;
	seq.push_back(0);
	Rebuild::flatten(i,seq);
	i=Rebuild::build(1,seq.size(),seq);
}

其他基本操作

插入

插入（Insert）一个元素，与二叉搜索树类似，不过需要在递归完后上推数据，还需要判断是否失衡，如果失衡，那么就重构。

代码：

void newnode(int &i,int v){// 新建节点
	i=(++tot);
	if(!root)root=i;
	t[i].init(v);
}

void insert(int &i,int v){
	if(!i){
		newnode(i,v);
		return;
	}
	if(t[i].w==v)t[i].cnt++;
	else if(t[i].w>v)insert(ls,v);
	else insert(rs,v);
	pushup(i);
	if(need_rebuild(i))rebuild(i);
}

删除

删除（Remove）一个元素，我们使用其他大多数平衡树使用的【懒删除】策略。只是将沿途的 \(\texttt{sz}\) 减 \(1\)。如果到了要删除的节点，那么也要将 \(\texttt{cnt}\) 减 \(1\)。最后和插入一样，也需要上推数据和判断失衡。

代码：

void remove(int &i,int v){
	if(!i)return;
	t[i].sz--;
	if(t[i].w==v){
		if(t[i].cnt>0)t[i].cnt--;
		return;
	}
	if(t[i].w>v)remove(ls,v);
	else remove(rs,v);
	pushup(i);
	if(need_rebuild(i))rebuild(i);
}

查询排名，查询排名对应的元素，查前驱，查后继

这一部分和二叉搜索树一模一样。就不讲了，只贴代码：

int kth(int &i,int k){
	if(!i)return 0;
	if(t[ls].sz>=k)return kth(ls,k);
	if(t[ls].sz<k-t[i].cnt)return kth(rs,k-t[ls].sz-t[i].cnt);
	return t[i].w;
}

int rnk(int &i,int v){
	if(!i)return 1;
	if(t[i].w>v)return rnk(ls,v);
	if(t[i].w<v)return rnk(rs,v)+t[ls].sz+t[i].cnt;
	return t[ls].sz+1;
}

int upper_bound(int &i,int v,bool great=0){
	if(!i)return !great;
	if(t[i].w==v&&t[i].cnt>0)return t[ls].sz+(!great)*(t[i].cnt+1);
	if(!great){
		if(v<t[i].w)return upper_bound(ls,v);
		return upper_bound(rs,v)+t[ls].sz+t[i].cnt;
	}
	if(t[i].w<v)return upper_bound(rs,v,1)+t[ls].sz+t[i].cnt;
	return upper_bound(ls,v,1);
}

int pre(int &i,int v){
	return kth(i,upper_bound(i,v,1));
}

int next(int &i,int v){
	return kth(i,upper_bound(i,v));
}

P6136 【模板】普通平衡树（数据加强版）

模板题，代码如下：

显示代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace ScapegoatTree{
#define ls (t[i].l)
#define rs (t[i].r)
	struct node{
		int s,sz,sd,cnt,l,r,w;
		void init(int weight){
			w=weight;
			l=r=0;
			s=sz=sd=cnt=1;
		}
	} t[10000005];
	int root,tot;
	const double alpha=0.7;
	
	void pushup(int i){
		t[i].s=t[ls].s+t[rs].s+1;
		t[i].sz=t[ls].sz+t[rs].sz+t[i].cnt;
		t[i].sd=t[ls].sd+t[rs].sd+(t[i].cnt>0);
	}
	
	bool need_rebuild(int i){
		if(t[i].cnt==0)return false;
		if(alpha*t[i].s<=(double)(max(t[ls].s,t[rs].s)))return true;
		if((double)t[i].sd<=alpha*t[i].s)return true;
		return false;
	}
	
	namespace Rebuild{
		void flatten(int i,vector<int> &seq){
			if(!i)return;
			flatten(ls,seq);
			if(t[i].cnt)seq.push_back(i);
			flatten(rs,seq);
		}
		int build(int l,int r,const vector<int> &seq){
			if(l==r)return 0;
			int mid=(l+r)>>1;
			int i=seq[mid];
			ls=build(l,mid,seq);
			rs=build(mid+1,r,seq);
			pushup(i);
			return i;
		}
	}
	
	void rebuild(int &i){
		vector<int> seq;
		seq.push_back(0);
		Rebuild::flatten(i,seq);
		i=Rebuild::build(1,seq.size(),seq);
	}
	
	void newnode(int &i,int v){
		i=(++tot);
		if(!root)root=i;
		t[i].init(v);
	}
	
	void insert(int &i,int v){
		if(!i){
			newnode(i,v);
			return;
		}
		if(t[i].w==v)t[i].cnt++;
		else if(t[i].w>v)insert(ls,v);
		else insert(rs,v);
		pushup(i);
		if(need_rebuild(i))rebuild(i);
	}
	
	void remove(int &i,int v){
		if(!i)return;
		t[i].sz--;
		if(t[i].w==v){
			if(t[i].cnt>0)t[i].cnt--;
			return;
		}
		if(t[i].w>v)remove(ls,v);
		else remove(rs,v);
		pushup(i);
		if(need_rebuild(i))rebuild(i);
	}
	
	int kth(int &i,int k){
		if(!i)return 0;
		if(t[ls].sz>=k)return kth(ls,k);
		if(t[ls].sz<k-t[i].cnt)return kth(rs,k-t[ls].sz-t[i].cnt);
		return t[i].w;
	}
	
	int rnk(int &i,int v){
		if(!i)return 1;
		if(t[i].w>v)return rnk(ls,v);
		if(t[i].w<v)return rnk(rs,v)+t[ls].sz+t[i].cnt;
		return t[ls].sz+1;
	}
	
	int upper_bound(int &i,int v,bool great=0){
		if(!i)return !great;
		if(t[i].w==v&&t[i].cnt>0)return t[ls].sz+(!great)*(t[i].cnt+1);
		if(!great){
			if(v<t[i].w)return upper_bound(ls,v);
			return upper_bound(rs,v)+t[ls].sz+t[i].cnt;
		}
		if(t[i].w<v)return upper_bound(rs,v,1)+t[ls].sz+t[i].cnt;
		return upper_bound(ls,v,1);
	}
	
	int pre(int &i,int v){
		return kth(i,upper_bound(i,v,1));
	}
	
	int next(int &i,int v){
		return kth(i,upper_bound(i,v));
	}
}

int last=0,ans=0;

signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int m,n;cin>>m>>n;
	while(m--){
		int v;cin>>v;ScapegoatTree::insert(ScapegoatTree::root,v);
	}
	while(n--){
		int op,x;
		cin>>op>>x;
		x^=last;
		if(op==1)ScapegoatTree::insert(ScapegoatTree::root,x);
		if(op==2)ScapegoatTree::remove(ScapegoatTree::root,x);
		if(op==3)last=ScapegoatTree::rnk(ScapegoatTree::root,x);
		if(op==4)last=ScapegoatTree::kth(ScapegoatTree::root,x);
		if(op==5)last=ScapegoatTree::pre(ScapegoatTree::root,x);
		if(op==6)last=ScapegoatTree::next(ScapegoatTree::root,x);
		if(op==3||op==4||op==5||op==6){
			ans^=last;
		}
	}
	cout<<ans;
	return 0;
}

标签：sz,cnt,return,seq,int,替罪羊,笔记,学习,ls
From： https://www.cnblogs.com/zheyuanxie/p/scapegoat-tree.html

前言

约定