替罪羊树

前置知识：二叉搜索树（建议没学过的先去学，很多操作都只有小修改，会更容易理解）
替罪羊树是基于权值 $\alpha$ ，由暴力重构实现并保证平衡的的一颗二叉搜索树。其基本是依靠 $\alpha$ 因子暴力重构实现平衡。并且它与普通的二叉搜索树的不同还有：二叉搜索树是将相同值放入一个节点并统计出现次数，而替罪羊树为了重构操作，将相同值的元素分别分配一个节点，以便于重构时操作
注意：以下所有的区间操作均为闭区间操作，请注意范围 $[l, r]$ 。并且所有的游标均为 $[1, index]$ 范围有效， $0$ 节点默认不使用。并且会频繁使用传引用，请务必看清楚使用区域。并且根节点有可能变化，不一定恒为节点 $1$ ，所以请使用变量记录根节点编号
基础变量名如下：

int n, root;//点的数目、根节点编号
int tot,  Void[N + 5];//内存池及配套的游标
int cnt, cur[N + 5];//重构时使用的临时数组及配套的游标
const double alpha = 0.75;//比例权值

struct Scapegoat {
    int lson, rson;//左、右子节点
    int exist; //该点是否存在
    int val; //该点的值
    int fac; //实际节点数
    int size;//含删除节点数的全部节点数
} tree[N];

inline bool check(int node);//判断以node点是否需要重构
inline void pushup(int node);//上传操作，注意：这里与线段树的上传操作有一点不同    
inline void build(int node);//重置节点大小、左右子节点

void dfs(int node);//中序遍历点
void setup(int &node, int l, int r);//重建树
void rebuild(int &node);//重建操作

void check_rebuild(int &node, int value);//判断value插入后是否需要平衡，是则进行平衡
void Insert(int &node, int value);//插入

int quary_rank(int value);//查询value的排名
int quary_num(int rank);//查寻rank排名的值

void erase(int node, int rank);//删除排名为rank的值的节点
void del(int value);//删除值为value的节点

终于是学完了替罪羊树，前前后后大概用了三天时间，从一开始拿权值线段树水过去这道模板题，到后来去学替罪羊树之间还发生了不少事情，敲替罪羊树时发生了但不限于如下的事情
看不懂操作，导致重新回去学了一遍二叉搜索树
重构时，临时数组记录了 $value$ 导致重构点越界
线段树入脑， $pushup$ 不加 $1$ ，导致疯狂 $WA$
$check$ 函数经常性写错大小符号，导致不该重构的时候重构，该重构的时候不重构
递归左右节点写错导致疯狂 $MLE，WA$ ，不仅是递归时写错，而且减 $rank$ 的时候还经常减了右子树的 $fac$ 。

~~希望各位引以为戒~~

$\alpha$ 因子

替罪羊树的核心，实质为一个比例常数，树的重量定义为 $k = \frac {max({size_{lson}, size_{rson}})} {size_{root}}$ 当 $k \ge \alpha$ 时，重构以 $root$ 为根的树
一般取 $\alpha = 0.7$ 或 $0.8$ ，以实现最高效率。额外多提一句： $0.5\le \alpha \le 1.0$ ，当取 $0.5$ 时会要求十分严格，重构会非常多。当取 $1.0$ 时，不可能引起树的重构，因为没有一棵树的根节点的大小小于子树节点
下面为判断以 $root$ 为根的子树是否平衡的代码

inline bool check(int node) {//判断是否需要重构
    return !(tree[node].fac * alpha > (double)max(tree[tree[node].lson].fac, tree[tree[node].rson].fac));
}//即：根的节点数 * 比例系数 > 子树最大节点数时，确定平衡

内存池机制

因为替罪羊树会有一定的重构操作，所以会频繁的收回一个节点编号，并且再分配节点编号。而常规的计数分配编号在这种操作下显然重复利用原有编号效率太低，所以我们引入内存池机制来高效的分配节点编号
我们这里定义一个数组 $Void$ 去存储还未分配的节点编号，并且使用一个配套游标去访问内存池内最顶部的编号
下面是内存池的相应机制对应的代码

int tot,  Void[N + 5];//内存池及对应游标

tot = 0;
for (int i = 1; i <= n; ++i) Void[++tot] = n - i + 1;//初始化内存池

node = Void[tot--];//在内存池内取编号

Void[++tot] = node;//在内存池中加入被删除的编号

删除操作

值得一提的是，替罪羊树的删除操作并不像二叉搜索树一样真正的去删除一个元素。替罪羊树利用了类似线段树的懒标记去标记一个数是否删除，这样就可以避免操作时无比麻烦的提取更换操作，并且避免过多的重构提高效率
但是过多的标记删除节点占比太多会影响效率，所以我们在删除时，同样去判断删除前的大小 $size$ 与删除后的大小 $Fac$ 的比重，判断是否需要重构。这样就可以避免过多的重构
由于使用标记删除，在下面的查询、重构等操作中都需要去判定是否存在这个点，然后再进行运算

void erase(int node, int rank) {
    --tree[node].fac;//减小实际的节点数
    if(tree[node].exist && (tree[tree[node].lson].fac + 1 == rank)) {
        tree[node].exist = 0;//将它标记为已删除
        return;
    }
    if(tree[tree[node].lson].fac >= rank) erase(tree[node].lson, rank);
    else erase(tree[node].rson, rank - (tree[tree[node].lson].fac + tree[node].exist) ); 
}

void del(int value) {
    erase(root,quary_rank(value));
    if(tree[root].size * alpha > (double)tree[root].fac) rebuild(root);//当删除节点占比过多，进行重构
}

重构子树

重构以 $root$ 为根节点编号的子树，我们需要中序遍历这颗子树，并且在遍历的过程中将元素编号记录在临时重构使用的 $cur$ 数组内，这样可以使得 $cur$ 数组内编号代表的值为升序排列
在重构时，我们将 $cur$ 中间的数取出作为根节点，然后建立左右子树
注意：我们在重构时是记录节点编号到数组内，而不是记录节点的值，如果记录节点值，重建时会引起访问非法节点

inline void pushup(int node) {
    tree[node].size = tree[tree[node].lson].size + tree[tree[node].rson].size + 1;
    tree[node].fac = tree[tree[node].lson].fac + tree[tree[node].rson].fac + 1;//注意+1 代表自己这个点也算
}

inline void build(int node) {//重置节点值
    tree[node].lson = tree[node].rson = 0;
    tree[node].size = tree[node].fac = 1;
}

void dfs(int node) {//中序遍历
    if(!node) return;
    dfs(tree[node].lson);
    if(tree[node].exist) cur[++cnt] = node;//待重建节点
    else Void[++tot] = node;//回收节点
    dfs(tree[node].rson);
}

void setup(int &node, int l, int r) {//重建
    int mid = l + r >> 1;
    node = cur[mid];//取中间节点，使得重建树尽可能平衡
    if(l == r) {
        build(node);
        return;
    }
    if(l < mid) setup(tree[node].lson, l, mid - 1);
    else tree[node].lson = 0;//建左子树
    if(r > mid) setup(tree[node].rson, mid + 1, r);
    else tree[node].rson = 0;//建右子树
    pushup(node);//上传节点
}

void rebuild(int &node) {//重建操作
    cnt = 0;
    dfs(node);
    if(cnt) setup(node, 1, cnt);
    else node = 0;
}

插入

在讲完替罪羊树的重构后，接下来的操作就比较简单了，这里先将插入操作
插入的大体操作与二叉搜索树一致，只不过替罪羊树将相同值的点进行了拆分，使得相同值的节点可以有多个。并且在插入完成后，要从根节点出发，向插入位置前进，找到深度最小（也就是距离根越近的）的不平衡节点进行重构

void Insert(int &node, int value) {
    if(!node) {
        node = Void[tot--];//分配节点
        tree[node].exist = 1, tree[node].val = value;
        build(node);
        return;
    }++tree[node].size, ++tree[node].fac;//注意：不能放最上面，会导致node为空时fac,size变化
    if(value <= tree[node].val) Insert(tree[node].lson, value);
    else Insert(tree[node].rson, value);
}

void check_rebuild(int &node, int value) {//自根开始检查平衡
    if(!node) return;
    if(check(node)) {
        rebuild(node);
        return;
    }
    if(value <= tree[node].val) check_rebuild(tree[node].lson, value);
    else check_rebuild(tree[node].rson, value);
}

查询

由于查询不会改变平衡性，所以查询直接依靠特点查询即可，和普通的二叉搜索树略有区别，但总体不难

int quary_rank(int value) {//返回value的排名
    int node = root, rank = 1;//从根节点开始,rank初始化为1
    while(node) {//遇空节点结束
        if(value <= tree[node].val) node = tree[node].lson;//查询左子树
        else rank += (tree[tree[node].lson].fac + tree[node].exist), node = tree[node].rson;//查询右子树
    }return rank;
}

int quary_num(int rank) {//查询排名为rank的数
    int node = root;//从根节点开始
    while(node) {//遇空节点结束
        if(tree[node].exist && tree[tree[node].lson].fac + 1 == rank) return tree[node].val;
        if(tree[tree[node].lson].fac >= rank) node = tree[node].lson;//查询左子树
        else rank -= (tree[tree[node].lson].fac + tree[node].exist), node = tree[node].rson;//查询右子树
    }return -1;//查找失败
}

模板题

洛谷 $P3369$ ，普通平衡树

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

const int N = 1e5 + 7;
const int M = 2e5 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;

int n, root;//点的数目、根节点编号
int tot,  Void[N + 5];//内存池及配套的游标
int cnt, cur[N + 5];//重构时使用的临时数组及配套的游标
const double alpha = 0.75;//比例权值

struct Scapegoat {
    int lson, rson;//左、右子节点
    int exist; //该点是否存在
    int val; //该点的值
    int fac; //实际节点数
    int size;//含删除节点数的全部节点数
} tree[N];

inline ll read() {
    ll s = 0, f = 1;
    char ch;
    do {
        ch = getchar();
        if (ch == '-') f = -1;
    } while (ch < 48 || ch > 57);
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * f;
}

inline bool check(int node);//判断以node点是否需要重构
inline void pushup(int node);//上传操作，注意：这里与线段树的上传操作有一点不同
inline void build(int node);//重置节点大小、左右子节点
void init(int n);//初始化

void dfs(int node);//中序遍历点
void setup(int &node, int l, int r);//重建树
void rebuild(int &node);//重建操作

void check_rebuild(int &node, int value);//判断value插入后是否需要平衡，是则进行平衡
void Insert(int &node, int value);//插入

int quary_rank(int value);//查询value的排名
int quary_num(int rank);//查寻rank排名的值

void erase(int node, int rank);//删除排名为rank的值的节点
void del(int value);//删除值为value的节点

signed main() {
    n = read();
    init(n);
    for(int i = 1; i <= n; ++i) {
        int op = read(), value = read();
        if(op == 1) {
            Insert(root, value);
            check_rebuild(root, value);
        }
        else if(op == 2) del(value);
        else  {
            ll ans;
            if(op == 3) ans = quary_rank(value);
            else if(op == 4) ans = quary_num(value);
            else if(op == 5) ans = quary_num(quary_rank(value) - 1);
            else ans = quary_num(quary_rank(value + 1));
            pr(ans);
        }
    }
    return 0;
}
void init(int n) {
    tot = 0;
    for(int i = 1; i <= n; ++i) Void[++tot] = n - i + 1;
}

inline void pushup(int node) {
    tree[node].size = tree[tree[node].lson].size + tree[tree[node].rson].size + 1;
    tree[node].fac = tree[tree[node].lson].fac + tree[tree[node].rson].fac + 1;//注意+1 代表自己这个点也算
}

inline void build(int node) {
    tree[node].lson = tree[node].rson = 0;
    tree[node].size = tree[node].fac = 1;
}

inline bool check(int node) {//判断是否需要重构
    return !(tree[node].fac * alpha > (double)max(tree[tree[node].lson].fac, tree[tree[node].rson].fac));
}//即：根的节点数 * 比例系数 > 子树最大节点数时，确定平衡

void check_rebuild(int &node, int value) {
    if(!node) return;
    if(check(node)) {
        rebuild(node);
        return;
    }
    if(value <= tree[node].val) check_rebuild(tree[node].lson, value);
    else check_rebuild(tree[node].rson, value);
}

void erase(int node, int rank) {
    --tree[node].fac;
    if(tree[node].exist && (tree[tree[node].lson].fac + 1 == rank)) {
        tree[node].exist = 0;
        return;
    }
    if(tree[tree[node].lson].fac >= rank) erase(tree[node].lson, rank);
    else erase(tree[node].rson, rank - (tree[tree[node].lson].fac + tree[node].exist) ); 
}

void del(int value) {
    erase(root, quary_rank(value));
    if(tree[root].size * alpha > (double)tree[root].fac) rebuild(root);//当删除节点占比过多，进行重构
}

void dfs(int node) {
    if(!node) return;
    dfs(tree[node].lson);
    if(tree[node].exist) cur[++cnt] = node;//待重建节点
    else Void[++tot] = node;//回收节点
    dfs(tree[node].rson);
}

void setup(int &node, int l, int r) {
    int mid = l + r >> 1;
    node = cur[mid];//取中间节点，使得重建树尽可能平衡
    if(l == r) {
        build(node);
        return;
    }
    if(l < mid) setup(tree[node].lson, l, mid - 1);
    else tree[node].lson = 0;//建左子树
    if(r > mid) setup(tree[node].rson, mid + 1, r);
    else tree[node].rson = 0;//建右子树
    pushup(node);
}

void rebuild(int &node) {
    cnt = 0;
    dfs(node);
    if(cnt) setup(node, 1, cnt);
    else node = 0;
}

void Insert(int &node, int value) {
    if(!node) {
        node = Void[tot--];//分配节点
        tree[node].exist = 1, tree[node].val = value;
        build(node);
        return;
    }++tree[node].size, ++tree[node].fac;//注意：不能放最上面，会导致node为空时fac,size变化
    if(value <= tree[node].val) Insert(tree[node].lson, value);
    else Insert(tree[node].rson, value);
}

int quary_rank(int value) {//返回value的排名
    int node = root, rank = 1;//从根节点开始,rank初始化为1
    while(node) {//遇空节点结束
        if(value <= tree[node].val) node = tree[node].lson;//查询左子树
        else rank += (tree[tree[node].lson].fac + tree[node].exist), node = tree[node].rson;//查询右子树
    }return rank;
}

int quary_num(int rank) {//查询排名为rank的数
    int node = root;//从根节点开始
    while(node) {//遇空节点结束
        if(tree[node].exist && tree[tree[node].lson].fac + 1 == rank) return tree[node].val;
        if(tree[tree[node].lson].fac >= rank) node = tree[node].lson;//查询左子树
        else rank -= (tree[tree[node].lson].fac + tree[node].exist), node = tree[node].rson;//查询右子树
    }return -1;//查找失败
}

学习笔记：替罪羊树

替罪羊树

因子

内存池机制

删除操作

重构子树

插入

查询

模板题

$\alpha$ 因子