1 概念
替罪羊树是一种平衡树，它维护平衡的方式不是旋转或者随机权值，而是最简单的暴力重构。当在插入和删除的时候发现某个节点子树失衡就暴力拍平重构，如此保证均摊复杂度 \(O(\log n)\)。
当然这种思想不止运用在平衡树中，还用于重构其它的数据结构。
2 基本操作
2.1 重构
既然是替罪羊树那么重点就是重构了。我们设定一个平衡因子 \(\alpha\)，来作为衡量一个子树是否平衡的标准。如果该节点的某一棵子树大小占整体大小的比例超过了 \(\alpha\)，我们就暴力重构整棵子树。
显然的，如果 \(\alpha\) 越小，那么建出来的树会更平衡，重构复杂度也会越高；反之建出来的树会不平衡，重构复杂度相对较低。极端的例子就是取 \(\alpha=0.5\) 或 \(1\)，但是这样做肯定不行。通常情况下我们选取 \(\alpha\in [0.7,0.85]\) 之间更优。
同时，由于替罪羊树采用的是惰性删除法（即不删除该节点，只将该节点上的出现次数减一），所以可能会有很多被删除的空节点，这些点同样会影响平衡。当未被删除的节点总数占整体大小的比例低于 \(\alpha\) 也要重构。
那么判断是否重构的代码如下：
struct ScapeGoat_Tree {
int l, r, val, cnt, s, sd, siz;
//左儿子、右儿子、该节点权值、权值出现次数、子树内节点数量、子树内未被删除的节点数量、子树内数字个数
}t[Maxn];
int tot = 0;
#define lp (t[p].l)
#define rp (t[p].r)
void pushup(int p) {//上传
t[p].s = t[lp].s + t[rp].s + 1;
t[p].sd = t[lp].sd + t[rp].sd + (t[p].cnt != 0);
t[p].siz = t[lp].siz + t[rp].siz + t[p].cnt;
}
double alpha = 0.75;//平衡因子
bool isreb(int p) {//判断是否需要重构
return ((double)max(t[lp].s, t[rp].s) >= alpha * t[p].s || alpha * t[p].s >= (double)t[p].sd);
}
接下来就是如何重构了，我们先将这棵子树进行中序遍历，得到该子树对应的序列，然后再用这个序列重建树即可。代码如下：
int nd[Maxn], cnt = 0;//记录中序遍历的节点
void flatten(int p) {//拍平操作
if(!p) return ;
flatten(lp);
if(t[p].cnt) nd[++cnt] = p;//没删除就加入
flatten(rp);
}
void build(int &p, int l, int r) {//重建树
if(l > r) {
p = 0;
return ;
}
int mid = (l + r) >> 1;
p = nd[mid];
build(lp, l, mid - 1), build(rp, mid + 1, r);
pushup(p);
}
void rebuild(int &p) {//重构
cnt = 0;
flatten(p);
build(p, 1, cnt);
}
2.2 插入
接下来的部分就很简单了。插入我们直接从根节点暴力向下走，判断与当前节点关系即可。注意在插入完之后就要对节点进行判断并重构。代码如下：
void ins(int &p, int x) {
if(!p) {
p = ++tot;
t[p] = {0, 0, x, 1, 1, 1, 1};
return ;
}
if(x == t[p].val) t[p].cnt++;
else if(x < t[p].val) ins(lp, x);
else ins(rp, x);
pushup(p);
if(isreb(p)) rebuild(p);
}
但是实际上这个做法还有一些优化空间，当没有删除操作的时候，我们可能会对两个有祖先关系的点都做一次重构，显然这样是不优的。所以我们可以在插入时找到最浅的需要被重构的节点，然后只重构这个节点即可。但是有删除操作的时候重构儿子就有可能让原本不平衡的祖先变平衡，所以不太适用这个做法。
2.3 删除
上文已经说过，替罪羊树的删除采用惰性删除，我们只需要找到对应节点并令其 cnt 减一即可，注意仍然需要判断重构。代码如下：
void del(int &p, int x) {
if(t[p].val == x) t[p].cnt--;
else if(x < t[p].val) del(lp, x);
else del(rp, x);
pushup(p);
if(isreb(p)) rebuild(p);
}
2.4 完整代码
剩下的无非就是查排名、查值、查前驱后继，按照一般平衡树的写法写就行。模板题代码如下：
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 2e5 + 5;
const int Inf = 2e9;
int n;
int rt;
namespace BST {
struct ScapeGoat_Tree {
int l, r, val, cnt, s, sd, siz;
}t[Maxn];
int tot = 0;
#define lp (t[p].l)
#define rp (t[p].r)
void pushup(int p) {
t[p].s = t[lp].s + t[rp].s + 1;
t[p].sd = t[lp].sd + t[rp].sd + (t[p].cnt != 0);
t[p].siz = t[lp].siz + t[rp].siz + t[p].cnt;
}
double alpha = 0.75;
bool isreb(int p) {
return ((double)max(t[lp].s, t[rp].s) >= alpha * t[p].s || alpha * t[p].s >= (double)t[p].sd);
}
int nd[Maxn], cnt = 0;
void flatten(int p) {
if(!p) return ;
flatten(lp);
if(t[p].cnt) nd[++cnt] = p;
flatten(rp);
}
void build(int &p, int l, int r) {
if(l > r) {
p = 0;
return ;
}
int mid = (l + r) >> 1;
p = nd[mid];
build(lp, l, mid - 1), build(rp, mid + 1, r);
pushup(p);
}
void rebuild(int &p) {
cnt = 0;
flatten(p);
build(p, 1, cnt);
}
void ins(int &p, int x) {
if(!p) {
p = ++tot;
t[p] = {0, 0, x, 1, 1, 1, 1};
return ;
}
if(x == t[p].val) t[p].cnt++;
else if(x < t[p].val) ins(lp, x);
else ins(rp, x);
pushup(p);
if(isreb(p)) rebuild(p);
}
void del(int &p, int x) {
if(t[p].val == x) t[p].cnt--;
else if(x < t[p].val) del(lp, x);
else del(rp, x);
pushup(p);
if(isreb(p)) rebuild(p);
}
int rnk(int p, int x) {//查有多少个数比 x 小
if(!p) return 0;
if(t[p].val == x && t[p].cnt) return t[lp].siz;
else if(t[p].val < x) return t[lp].siz + t[p].cnt + rnk(rp, x);
else return rnk(lp, x);
}
int kth(int p, int k) {//查第 k 小
if(!p) return 0;
if(t[lp].siz < k && k <= t[lp].siz + t[p].cnt) return t[p].val;
else if(k <= t[lp].siz) return kth(lp, k);
else return kth(rp, k - t[lp].siz - t[p].cnt);
}
int pre(int p, int x) {return kth(p, rnk(p, x));}//求前驱
int nxt(int p, int x) {return kth(p, rnk(p, x + 1) + 1);}//求后继
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
while(n--) {
int opt, x;
cin >> opt >> x;
switch(opt) {
case 1: {
BST::ins(rt, x);
break;
}
case 2: {
BST::del(rt, x);
break;
}
case 3: {
cout << BST::rnk(rt, x) + 1 << '\n';
break;
}
case 4: {
cout << BST::kth(rt, x) << '\n';
break;
}
case 5: {
cout << BST::pre(rt, x) << '\n';
break;
}
case 6: {
cout << BST::nxt(rt, x) << '\n';
break;
}
}
}
return 0;
}
2.5 例题
你可能会觉得，替罪羊树这种暴力方法不会比其它的平衡树好上多少，也不会有什么突出的优点。但事实上，由于其采用重构而非旋转或随机权值，在需要信息稳定维护的时候它还有自己的用武之地。
例 1 [湖北省队互测2014] 没有人的算术
这道题还是比较好的。考虑到问题的难点就在于比较两个数对的大小，如果可以快速的求解这个，我们就可以用线段树简单的实现剩下的部分了。
我们现在考虑给每一个已经得到的数对赋上一个权值，然后这个权值正好可以代表数对间的大小关系。例如将 \((0,0)\to 1\)，\((0,(0,0))\to (0,1)\to 2\)，\(((0,0),0)\to (1,0)\to 3\)。接下来就考虑怎样表示这个，我们建出一棵二叉搜索树，然后将当前需要插入的数对从根节点开始往下走，找到它对应的位置。
接下来我们就需要让赋的值满足二叉搜索树的关系。我们在走的时候为每个节点再给一个关系区间 \([L,R]\)，把当前节点对应的数对的权值赋成 \(mid = \dfrac{L+R}2\)，然后左右儿子的管辖区间就是 \([L,mid]\) 和 \([mid, R]\)。不难发现按照这样来赋值，一定可以保证每个点的权值符合二叉搜索树的关系。
但是此时有一个问题，就是如果这棵树深度过大，我们的权值的精度也会很大。具体的，如果树是一条链，那么我们所需的精度就是 \(2^n\) 级别的。显然这难以实现。于是我们就要让深度尽可能小，也就是让他成为一颗平衡树，然后我们的精度就只需要 \(2^{\log_2 n}\) 也就是 \(n\) 级别的了。
不过这个平衡树并不是普通的平衡树，因为我们要维护节点的管辖区间和权值，如果采用旋转或者分裂合并来实现的话会发现较为困难，此时就要使用替罪羊树这种基于重构的平衡树来维护了。
3 重构数据结构
替罪羊树这种设定平衡因子来调整平衡性的方法并不局限于平衡树，事实上其它数据结构也可以利用到它。下面举几个经典的例子。
3.1 重构 K-D Tree
在 \(\text{K-D Tree}\) 那一章节的文章中，我们提到了对于插入操作如何处理。虽然替罪羊式的重构并不能完全保证其矩阵查询时 \(O(n^{1-\frac 1k})\) 的复杂度，但是在一般情况下也够用了。
具体的，我们仍然设一个平衡因子 \(\alpha\)，然后判断当前子树是否需要重构。如果是，直接暴力拍平整棵子树，然后按照静态建 \(\text{K-D Tree}\) 的方式重构即可。对于插入，我们将当前点从根节点开始往下走放到对应位置即可；对于删除仍然采用惰性删除法。
实际上这样做与二进制分组所需要实现的功能是一致的，即拍平和重构，核心代码如下：
int tot = 0;
int trs[Maxn], top;//用垃圾桶回收节点
void del(int &p) {
trs[++top] = p;
t[p] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
p = 0;
}
int newnode() {
return top ? trs[top--] : ++tot;
}
const double alpha = 0.85;
bool isreb(int p) {//是否需要重构
return alpha * t[p].siz <= (double)max(t[lp].siz, t[rp].siz);
}
node nd[Maxn];
int cnt;
void flatten(int &p) {//暴力拍平
if(!p) return ;
flatten(lp);
nd[++cnt] = {t[p].v[0], t[p].v[1], t[p].val};//这里不需要管遍历顺序，只要存下来点即可
flatten(rp);
del(p);
}
void build(int &p, int l, int r, int typ) {//静态构建 K-D Tree
if(l > r) return p = 0, void();
int mid = (l + r) >> 1;
nth_element(nd + l, nd + mid, nd + r + 1, [typ](node x, node y){return x.v[typ] < y.v[typ];});
p = newnode();
t[p].v[0] = nd[mid].v[0], t[p].v[1] = nd[mid].v[1], t[p].val = nd[mid].val, t[p].siz = 1;
build(lp, l, mid - 1, typ ^ 1), build(rp, mid + 1, r, typ ^ 1);
pushup(p);
}
void rebuild(int &p) {
cnt = 0;
flatten(p);
build(p, 1, cnt, 0);
}
void ins(int &p, node x, int typ) {
if(!p) {
p = newnode();
t[p] = {0, 0, x.v[0], x.v[1], x.v[0], x.v[1], x.v[0], x.v[1], x.val, x.val, 1};
return ;
}
if(t[p].v[0] == x.v[0] && t[p].v[1] == x.v[1]) t[p].val += x.val;
else if(x.v[typ] < t[p].v[typ]) ins(lp, x, typ ^ 1);
else ins(rp, x, typ ^ 1);
pushup(p);
if(isreb(p)) rebuild(p);//插入后看是否需要重构
}
3.2 重构点分树
我们知道带修改处理树上路径的一类题目可以采用点分树来求解，但是如果这棵树的形态本身还在变化，我们就得单次重建点分树来求解，显然这样不够优秀。
此时就考虑运用替罪羊树的思想，我们单次插入一个点的时候直接将它与父亲连边，依然设一个平衡因子 \(\alpha\)，如果一个子树占它父亲的子树的比例超过 \(\alpha\)，则暴力重构它的父亲。而所谓暴力重构就是重新跑一遍点分树然后维护对应信息。
值得注意的是重构点分树的时候找出要重构的子树，如果把点分树直接建出来的话不算困难，但是如果你只记录了点分树上的父亲然后在原树上找重构子树的话需要注意，点分树上的子树在原树上只是一个连通块，其边界是不明确的，所以找的时候要判断是否还在该子树内，这个可以通过判断点分树上的深度来实现。
这样的话点分树就可以支持动态插入了，你可以理解为 “动态点分树”。
例 2 [WC2014] 紫荆花之恋
可以称得上是重构点分树的经典题了。先考虑朴素解法，建立点分树然后枚举 \(\text{LCA}\)，假设当前枚举到 \(p\)，那么条件就是 \(dis(i,p)+dis(p,j)\le r_i+r_j\)，转化一下就是 \(dis(p,j)-r_j\le r_i-dis(i,p)\)。接下来按照套路，对每个节点 \(x\) 开两颗平衡树，分别维护子树内所有点的 \(dis(x,i)-r_i\) 的值以及 \(dis(fa_x,i)-r_i\) 的值，查询的时候直接查排名即可。
加上动态插入的要求的话做点分树重构即可。看上去思路挺简单，但是细节比较多，这里列举几条：
- 由于重构的时候要清空平衡树，所以在平衡树上需要开垃圾桶防止空间爆炸。
- 发现此题中单次重构点分树的复杂度为 \(O(n\log^2 n)\)，复杂度较高，因此平衡因子应该取大一点，比如取 \(\alpha=0.85\)。同时应该使用上文所说的优化方式来重构，即取最浅的需要重构的节点来重构。
- 平衡树尽量不要用常数巨大的 \(\text{FHQ-Treap}\)，可以用替罪羊树来写。