Scapegoat Tree: A Brief Tutorial

重量平衡树：BST

重量平衡树首先是平衡树，其次保证形态的同时优先保证了子树的重量（size）是期望优的。
除了替罪羊树一个例子是Treap。
相关概念可参考[1]。

重量平衡树：The Satisfying Case

Not only what general BST satisifying, but also

maintaining the value set of subtrees
maintaining (almost every) union sets of the info sets of the subtrees on a node
...

In general BSTs, when we rotate the tree, we need to recalculate the union sets, which costs $ O(n) $ time.

Scapegoat Tree: The Definition

Balanced Factor: $ \alpha $

我们定义一个常量 $ \alpha \in (0,1) $ ，$ size(o) $指以$ o $ 为根子树有效结点个数，则称满足 $ size(lc(o)) > size(o) \cdot \alpha \lor size(rc(o)) > size(o) \cdot \alpha $ 的节点是不平衡的。
实现中一般选取alpha = 0.75。

Keeping Balance: Reconstruction

由于我们不使用旋转操作保证整棵树的平衡，所以我们考虑对所有不平衡的节点，我们暴力重构以其为根的子树。容易发现，当所有节点均为平衡的时，整棵树满足 BST 的定义，也即期望深度为 $ O(\lg n) $。

Erasing Node: Lazy-tagging

对于每次删除节点的操作，我们不直接从原树中删除，而是使用(bool)exist进行标记。当一个点 $ size < total \cdot \alpha $时，也认为其不平衡的，暴力重构。

The Complexity: Time/Space

树的期望深度是 $ \log_{1/\alpha} n $的。所以仍然保证其他操作复杂度仍为对数级别。
使用内存回收的话，空间也是 $ O(n) $ 级别的。

Scapegoat Tree: The Code (Template)

BZOJ 3224(3948 kb 304 ms)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}

const double alpha = 0.75;
const int maxn = 1e5 + 100;
struct Node
{
    int ch[2];
    int v, size, total;
    bool exist;
} pool[maxn];
int pcnt = 1, tag, root = 0;
int sta[maxn], st = 0;
#define lc(o) (pool[o].ch[0])
#define rc(o) (pool[o].ch[1])
#define v(o) (pool[o].v)
#define size(o) (pool[o].size)
#define total(o) (pool[o].total)
#define exist(o) (pool[o].exist)
inline void maintain(int o)
{
    size(o) = size(lc(o)) + size(rc(o)) + exist(o);
    total(o) = total(lc(o)) + total(rc(o)) + 1;
}
inline bool check(int o)
{
    return (double)total(o) * alpha < (double)total(lc(o)) || (double)total(o) * alpha < (double)total(rc(o));
}
void ins(int &o, int x)
{
    if(!o)
    { 
        if(st) o = sta[--st];
        else o = pcnt++;
        pool[o] = (Node){{0, 0}, x, 1, 1, true};
    }
    else
    {
        if(x <= pool[o].v) ins(lc(o), x);
        else ins(rc(o), x);
        maintain(o); if(check(o)) tag = o;
    }
}
int a[maxn], ac = 0;
void deconstruct(int o, bool first = true)
{
    if(!o) return;
    deconstruct(lc(o), false);
    if(exist(o)) a[ac++] = pool[o].v;
    deconstruct(rc(o), false);
    if(!first) sta[st++] = o;
}
void construct(int &o, int L = 1, int R = ac - 1)
{
    if(L > R) return;
    int M = (L + R) >> 1;
    if(!o && st) o = sta[--st];
    else if(!o) o = pcnt++;
    pool[o] = (Node){{0, 0}, a[M], 1, 1, true};
    construct(lc(o), L, M - 1), construct(rc(o), M + 1, R), maintain(o);
}
void reconstruct(int &o)
{
    ac = 1;
    deconstruct(o);
    construct(o);
}
inline void insert(int x){tag = 0; ins(root, x); if(tag) reconstruct(tag);}
void del(int o, int x)
{
    if(!o) return;
    if(exist(o) && size(lc(o)) + exist(o) == x)
    {
        exist(o) = false, maintain(o);
        return;
    }
    if(size(lc(o)) + exist(o) < x)
    {
        del(rc(o), x - size(lc(o)) - exist(o));
    }
    else
    {
        del(lc(o), x);
    }
    maintain(o);
}
int Rank(int x)
{
    int o = root, ans = 1;
    while(o)
    {
        if(v(o) >= x) o = lc(o);
        else ans += size(lc(o)) + exist(o), o = rc(o);
    }
    return ans;
}
int kth(int x)
{
    int o = root;
    while(o)
    {
        if(size(lc(o)) + exist(o) == x && exist(o)) return v(o);
        if(size(lc(o)) + exist(o) >= x) o = lc(o);
        else x -= size(lc(o)) + exist(o), o = rc(o);
    }
}
inline void del(int x)
{
    del(root, Rank(x));
    if((double)size(root) < alpha * (double)total(root)) reconstruct(root);
}
int main()
{
    int n; read(n);
    while(n--)
    {
        int opt, x; read(opt, x);
        if(opt == 1) insert(x);
        else if(opt == 2) del(x);
        else if(opt == 3) printf("%d\n", Rank(x));
        else if(opt == 4) printf("%d\n", kth(x));
        else if(opt == 5) printf("%d\n", kth(Rank(x) - 1));
        else printf("%d\n", kth(Rank(x + 1)));
    }
    return 0;
}

The Advantages

对于一类在线添加节点，而树的形态相对固定，且子树信息难以高效统计（合并，但可以高效添加），替罪羊是一个很好的选择。
例子：后缀平衡树和动态点分治的“重心树”。

The Disadvantages

对于连续序列的操作，替罪羊树显得不在行。
它不支持抽取一段连续的区间并对其进行统计/修改/翻转等旋转平衡树常见操作。

参考 References

[1] 陈立杰.重量平衡树和后缀平衡树在信息学奥赛中的运用.2013年信息学奥林匹克中国国家队候选队员论文.2013

替罪羊树 Scapegoat Tree