本文共 4802 字，大约阅读时间需要 16 分钟。

0.链接

以往我都是把链接放在最后面的。后来我想了想，这样是不道德的，欺骗读者先看自己的垃圾文章，再看真正带劲的博客！

所以，在这里了，是一篇洛谷的博客。

1.概述

然而还是一种二叉平衡树……好处是不用旋转。

2.思想

2.1.保持平衡

众所周知，时间复杂度得靠平衡来保证。如果你不旋转，为什么能够保持平衡呢？

我们来看另一个例子，时间复杂度非常稳定，算法的流程是——

• 请注意，这不是要介绍新算法，尽管它的复杂度是很有保障的，而且代码复杂度极低。但是！你即使学到了这种算法，也要坚持把这篇博客讲述的 替罪羊树 看完，因为技多不压身。
• 请注意，学完之后，你不要忘记最初点进这篇博客的原因，因为你知道，这篇博客说不定有点帮助呢？所谓兼听则明、偏听则暗，永远不要只看一家之言，最好是博览群书，却不尽信书。
• 请注意，这是一种不需要使用二叉平衡树的算法，不然，我们把它作为“二叉平衡树之替罪羊”的引路人有什么意义？但这也意味着，你得更用心地寻找这种方法蕴含的思想与今天的 替罪羊树 有什么关系。
• 请注意，我写这么多条是希望你认真思考如何让复杂度稳定下来，同时也是为了让你的情绪稳定下来。人不要总是充满好奇心，对自己仿佛从来没听说过的算法而兴奋。

——利用数组存储，插入排序，二分查找。

认错是不可能认错的。我错了，我真的错了。

好吧，进入正题：如果我们 暴力地将树重构为平衡的样子，它不就平衡了吗？就像那个小小的数组，每次都进行一次插入排序，使其有序（或者赋予其特殊结构、性质），所以可以 加快查询的速度。

然后就有了 替罪羊树 ，尽管你看不出这跟 替罪羊 有什么关系。

2.2.平衡因子

很显然，上面用数组实现的例子中，因为每一次都调整结构，所以很慢。

那么，放在 替罪羊树 上，我们需要对其进行改进，我们 减少重构的次数。

但是，别忘了，重构是必要的，否则树将会不平衡。为了在 平衡和重构次数之间找到平衡，我们定义了一个非常有意思的常数：平衡因子 $\alpha$ 。

我们只对 严重倾斜 的子树进行重构。其中，严重倾斜 的定义是：

$$\exists y\in son(x),size(y)>\alpha \cdot size(x)$$

很科学，不是吗？如果这颗子树的 $\alpha$ 都在某个儿子中，那就不是很平衡了。

一般来说，我们取 $\alpha \in [0.7,1)$ ，具体取决于使用场景。别忘了，重构的目的是加快查询，重构次数太多会使得插入极其缓慢。找到 $balance$ 即可！

2.3.惰性修改

一般的二叉平衡树，删除的时候就会直接将节点移除。但是，替罪羊树 非常讨厌结构的变化。

所以，我们把那些 $cnt=0$ 的节点给保留下来，以维持原有的结构。以后，某一次插入的时候，如果导致子树被重构，再把这些点剔除。

内在的道理是什么呢？我的理解是，替罪羊树 结构很完美（有如线段树），所以不需要对其结构进行修改。而其他的平衡树，都是 节点数量越少，速度越快，自然就这样了呗。

3.代码

直接到 代码 板块了吗？这么快？

但是也确实没有什么可以讲的了 😐

难道 开两个数组，一个存 节点 的数量，另一个存 元素 的数量 是需要专门拿出来说的吗？

难道 重构的时候，可以只重构最大的不平衡子树 也是值得一提的吗？

#include <cstdio>#include <iostream>#include <vector>#include <cstdlib>#include <algorithm>using namespace std;inline int readint() {   	int a = 0; char c = getchar(), f = 1;	for(; c<'0' or c>'9'; c=getchar())		if(c == '-') f = -f;	for(; '0'<=c and c<='9'; c=getchar())		a = (a<<3)+(a<<1)+(c^48);	return a*f;}# define MB template < typename T >MB void getMax(T &a,const T &b){    if(a < b) a = b; }MB void getMin(T &a,const T &b){    if(b < a) a = b; }const int MaxN = 300005;namespace SGT{    // ScapeGoatTree	int siz[MaxN]; // 节点数量	int data[MaxN]; // 元素大小	int cnt[MaxN]; // 元素数量	int alive[MaxN]; // 元素总数量	int son[MaxN][2]; // 儿砸	const double alpha = 0.72; // 平衡因子	bool bad(int o){    // 不平衡了！		if(siz[son[o][0]] > alpha*siz[o])			return true;		if(siz[son[o][1]] > alpha*siz[o])			return true;		return false;	}	void pushUp(int o){   		siz[o] = 1+siz[son[o][0]]+siz[son[o][1]];		alive[o] = alive[son[o][0]]+alive[son[o][1]];		alive[o] += cnt[o]; // 还活着几个	}	int cntNode;	int newNode(int val,int num){   		if(num <= 0) return 0;		int &id = ++ cntNode;		data[id] = val, siz[id] = 1;		cnt[id] = alive[id] = num;		return id;	}	int build(vector<int> &v,int l,int r){   		if(l == r) return 0; // [l,r)		int mid = (l+r)>>1, o = v[mid];		son[o][0] = build(v,l,mid);		son[o][1] = build(v,mid+1,r);		pushUp(o); return o;	}	void collect(vector<int> &v,int o){    // 收集子树内元素		if(o == 0) return ;		collect(v,son[o][0]);		if(cnt[o] != 0) // 还活着			v.push_back(o);		collect(v,son[o][1]);	}	void rebuild(int &o){   		static vector<int> v; v.clear();		collect(v,o), o = build(v,0,v.size());	}	void modify(int &o,int val,int addv,int &re){   		if(o == 0) return void(o = newNode(val,addv));		if(data[o] == val) getMax(cnt[o]+=addv,0);		else modify(son[o][data[o]<val],val,addv,re);		pushUp(o); if(bad(o)) re = o;	}	void adjust(int o,int val,int re){   		while(re != 0){   			int d = (data[o] < val);			if(re == son[o][d])				rebuild(son[o][d]), re = 0;			else o = son[o][d];		}	}	int root;	void modify(int val,int addv){   		int o = 0; modify(root,val,addv,o);		if(o == root) rebuild(root);		else adjust(root,val,o);	}	int getRank(int val){   		int o = root, res = 0;		for(int d; o!=0; o=son[o][d]){   			d = data[o] <= val;			res += d*(alive[son[o][0]]);			if(data[o] == val) break;			else res += d*cnt[o];		}		return res;	}	int count(int val){   		int o = root;		for(int d; o!=0; o=son[o][d]){   			d = data[o] < val;			if(data[o] == val) break;		}		return cnt[o];	}	int kthElement(int k){   		int o = root;		for(int d; o!=0; d=0){   			d = alive[son[o][0]]+cnt[o];			if(k >= alive[son[o][0]]){   				if(k < d) return data[o];				k -= d, o = son[o][1];			}			else o = son[o][0];		}		return 0.0/0.0; // 还你一个 NaN	}} using namespace SGT;int main(){   	for(int T=readint(),opt,x; T; --T){   		opt = readint(), x = readint();		if(opt == 1 or opt == 2)			modify(x,-2*opt+3);		if(opt == 3) printf("%d\n",getRank(x)+1);		if(opt == 4) printf("%d\n",kthElement(x-1));		if(opt == 5 or opt == 6){   			int rnk = getRank(x), d = -1;			if(opt == 6) d = count(x);			printf("%d\n",kthElement(rnk+d));		}	}	return 0;}

4.时间复杂度

里写的挺好的。真正的理性思维。

如何感性理解复杂度呢？对于一个大小为 $x$ 的子树，如果它需要重构，那么两个子树的大小之差至少达到 $(2\alpha -1)x$ 。也就是说，平衡 $\to$ 重构 $\to$ 平衡 的花费是 $x$，但是这也需要一个正比于 $x$ 的插入次数。那么重构的复杂度其实可以均摊到插入上。