1 从 BST 到平衡树

众所众知，二叉搜索树（BST）是一棵能方便实现插入、删除，找前驱、后驱，按排名找数、找数的排名的数据结构，但是在构造数据下，ta 的单次复杂度甚至有 \(O(N)\)。因此，平衡树就登场了，ta 的单次复杂度仅为 \(O(\log N)\)。
map/set 等 STL 的实现方式也是平衡树的一种——红黑树。

2 替罪羊树

2.1 替罪羊树的维护

替罪羊树就是比较优雅的暴力啦。
众所周知，一棵树不平衡了怎么办？重建呗（反正对于不同的二叉搜索树，其中序遍历不变）。例如：

中序遍历：\([1,2,3,4,5,6]\)。
重建：
此时，该 BST 就平衡了不少。
那么，我们只要在该树不平衡时，重建就可以了。
设某树的左子树有 \(lsize\) 个点（包括未删除的点，下同），右子树上有 \(rsize\) 个点，我们定义该树的不平衡率为 \(\alpha'=\dfrac{\max(lsize,rsize)}{lsize + rsize}\)。
显然，\(0.5 \le \alpha' \le 1\)（两种极端情况分别为：左右子树节点数相等、左右子树其中有一个子树为空），且 \(\alpha'\) 越大，该树越不平衡。
所以，我们只要设定一个阈值 \(\alpha\)，使得某树不平衡率 \(\alpha' > \alpha\) 时重建即可。
一般来说，\(\alpha\) 为 \(0.7\) 或 \(0.75\)。
还有一种情况，替罪羊树的删除是打标，而不真正删掉，所以当删除的节点个数为 \(del\)， \(\dfrac{del}{lsize + rsize} > \beta\) 时，也要重建。
同样的，一般来说，\(\beta\) 为 \(0.3\)。

2.2 替罪羊树的基本操作

2.2.1 替罪羊树的结点信息

lc、rc：左右儿子。不存在则为 \(-1\)。
fa：父亲。
val、cnt：结点的值及个数。
nodesize、avsize、numsize：该子树的总结点数目、未打标（也就是未删除）结点数目、存储的数字个数（也就是 \(\sum cnt\)）。
del：是否被删除。
root：树根。空树则为 \(-1\)。

    struct tNode
    {
        int lc, rc, fa, val, cnt, nodesize, avsize, numsize;
        bool del;
    }tree[N << 1];
    int root;
    Scapegoat_Tree() { root = -1; }

2.2.2 替罪羊树的空间利用

由于替罪羊树删除为打标，因此替罪羊树的空间利用是一个问题。
所以定义内存池（用栈实现）mem，使用 newmem 函数来新建节点，返回新结点的编号。用 used 表示到现在为止使用过（包括已删除）的结点的编号，inst 表示栈中结点数目。

    int used, inst;
    stack<int>mem;
    int newmem()
    {
        if(inst > 0) // 栈非空，弹出栈顶
        {
            inst--;
            int top = mem.top();
			mem.pop();
			return top;
        }
        return ++used; // 否则再建一个节点
    }

2.2.3 替罪羊树的重建

首先，最基础的，对于已知的位置，初始化点。

    void Add_Node(int nid, int val, int fa)
    {
        tree[nid].fa = fa, tree[nid].lc = tree[nid].rc = -1, tree[nid].val = val;
        tree[nid].cnt = tree[nid].nodesize = tree[nid].avsize = tree[nid].numsize = 1, tree[nid].del = false;
    }

找到某个值的位置。若不存在，返回一个结点，使得该值可作为该结点的左儿子或右儿子。

    int Find_Pos(int x, int val)
    {
        if(val < tree[x].val && tree[x].lc != -1) // 可能在左子树
            return Find_Pos(tree[x].lc, val);
        if(val > tree[x].val && tree[x].rc != -1) // 可能在右子树
            return Find_Pos(tree[x].rc, val);
        return x; // 找到目标结点
    }

还有 Update 函数，用来更新祖先结点的 nodesize、avsize、numsize，用 nodeadd、avadd、numadd 来表示祖先结点的 nodesize、avsize、numsize 需要加上的值。

    void Update(int x, int nodeadd, int avadd, int numadd)
    {
        if(x == -1) // 跳到头了
            return ;
        tree[x].nodesize += nodeadd, tree[x].avsize += avadd, tree[x].numsize += numadd;
        Update(tree[x].fa, nodeadd, avadd, numadd); // 向上跳
    }

然后就是替罪羊树的核心重建。
第一步是求中序遍历。

// 在结构体外
int seqsize;
struct tSeq
{
    int val, cnt;
}tseq[N << 1];

// 在结构体内
    void Dfs(int x)
    {
        if(x == -1) // 跳到了空结点
            return;
        Dfs(tree[x].lc); // 先遍历左子树
        if(!tree[x].del) // 如果未删除
            tseq[++seqsize].val = tree[x].val, tseq[seqsize].cnt = tree[x].cnt, mem.push(x), inst++;
        Dfs(tree[x].rc); // 最后遍历右子树
    }

ReAdd 函数，对区间 \([l, r]\) 进行重建，父节点为 fa，并返回根节点。

    int ReAdd(int l, int r, int fa)
    {
        if(l > r)
            return -1;
        int mid = (l + r) >> 1; // 取中间的结点
        int nid = newmem(); // 取出新的结点
        tree[nid].fa = fa;
		tree[nid].cnt = tseq[mid].cnt;
        tree[nid].val = tseq[mid].val;
        tree[nid].lc = ReAdd(l, mid - 1, nid); // 递归左边
        tree[nid].rc = ReAdd(mid + 1, r, nid); // 递归右边
        tree[nid].numsize = tree[tree[nid].lc].numsize + tree[tree[nid].rc].numsize + tseq[mid].cnt;
        tree[nid].nodesize = tree[nid].avsize = r - l + 1; // 注意已经自动删掉了打标了的结点
        return nid;
    }

ReBuild，对已知的结点 \(x\) 做重建。

    void ReBuild(int x)
    {
        seqsize = 0;
        Dfs(x);
        if(x == root)
            root = ReAdd(1, seqsize, -1);
        else
        {
            Update(x, tree[x].avsize - tree[x].nodesize, 0, 0);
            if(tree[tree[x].fa].lc == x)
                tree[tree[x].fa].lc = ReAdd(1, seqsize, tree[x].fa);
            else
                tree[tree[x].fa].rc = ReAdd(1, seqsize, tree[x].fa);
        }
    }

最后，当我们修改结点的时候，只有根结点到 \(val\) 代表的结点这一条路径上的结点可能会不平衡，所以从根节点开始，向下递归看是否要重建。

// 在结构体外
const double Alpha = 0.75, Beta = 0.3;

// 在结构体内
    void Find_ReBuild(int x, int val)
    {
        if(double(max(tree[tree[x].lc].nodesize, tree[tree[x].rc].nodesize)) > (tree[x].nodesize - 1) * Alpha || double(tree[x].nodesize - tree[x].avsize) > tree[x].nodesize * Beta) // 对应要重建的两种情况
        {
            ReBuild(x); // 重建
            return ;
        }
        if(tree[x].val != val) // 继续往下找
            Find_ReBuild((tree[x].val > val)?tree[x].lc:tree[x].rc, val);
    }

剩下的操作就很简单了。

2.2.4 替罪羊树的插入、删除

插入函数 Add，用 Find_Pos 函数找到位置，再讨论在何处插入。

    void Add(int val)
    {
        if(root == -1) // 为空树
        {
            Add_Node(root = newmem(), val, -1);
            return ;
        }
        int p = Find_Pos(root, val); // 找到应插入的位置
        if(tree[p].val == val) // 树中有这个结点
        {
            tree[p].cnt++;
            if(tree[p].del) // 删除了就复活
                tree[p].del = false, Update(p, 0, 1, 1);
            else
                Update(p, 0, 0, 1);
        }
        else if(tree[p].val > val) // 树中无该结点，判断新加的结点是左儿子还是右儿子
            Add_Node(tree[p].lc = newmem(), val, p), Update(p, 1, 1, 1);
        else
            Add_Node(tree[p].rc = newmem(), val, p), Update(p, 1, 1, 1);
		Find_ReBuild(root, val); // 判断是否重建
    }

删除函数 Del，也是用 Find_Pos 函数找到位置，再删除，判断是否打标。

    void Del(int val)
    {
        int p = Find_Pos(root, val); // 找到应删除的位置
        tree[p].cnt--;
        if(!tree[p].cnt) // 需要打标
            tree[p].del = true, Update(p, 0, -1, -1);
        else
            Update(p, 0, 0, -1);
        Find_ReBuild(root, val); // 判断是否重建
    }

2.2.5 替罪羊树的按数找排名、按排名找数

Find_Rank 函数，查找 \(val\) 的排名，从根节点递归查找。

    int Find_Rank(int val)
    {
        int x = root, ans = 0;
        while(tree[x].val != val)
        {
            if(x == -1) // 如果到了空树，那么 ans + 1 即为答案
                return ans + 1;
            if(val < tree[x].val) // 如果 val 比当前根的 val 小，那么在左子树
                x = tree[x].lc;
            else
                ans += tree[tree[x].lc].numsize + tree[x].cnt, x = tree[x].rc; // 否则在右子树，比 val 小的数有当前的左子树的 numsize + 当前根的 cnt
        }
        if(tree[x].lc != -1) // 左子树不为空，还有当前左子树的 numsize 没有算
            ans += tree[tree[x].lc].numsize;
        return ans + 1;
    }

Find_Num 函数，查找排名为 \(rank\) 的数，同样从根节点递归查找。

    int Find_Num(int rank)
    {
        int x = root, rrank = rank;
        while(true)
        {
            if(rrank <= tree[tree[x].lc].numsize) // 如果 rank 不大于左子树的 numsize，那么就是左子树的第 rank 个
                x = tree[x].lc;
            else // 否则要么是根，要么在右子树
            {
                rrank -= tree[tree[x].lc].numsize; // 先将 rank 减去左子树的 numsize
                if(rrank <= tree[x].cnt) // rank 小于等于根节点的 cnt，就在根节点
                    return tree[x].val;
                rrank -= tree[x].cnt, x = tree[x].rc; // 否则在右子树，根的值应该比答案小，减去根的 cnt
            }
        }
    }

2.2.6 替罪羊树的找前驱、后继

思维上略微复杂。
为了方便，定义 \(isrc(x)\) 表示 \(x\) 是否是一个结点的右儿子，是则为 \(1\)，不是则为 \(0\)。
首先用 Find_Pos 函数找到 \(val\) 的位置（记为 \(p\)），is_rc 表示上一个结点是否为该结点的右儿子。如果它是上一个结点是该结点的左儿子，一定往上跳（若答案在某个跳过的点的左子树上，答案不受影响），若是右儿子，那么如果比 \(val\) 小且存在，那么一定为该点，否则如果其有左儿子，在左儿子上找最大值。如果上述均不满足，那么往上跳 \(^\dag\)。
\(^\dag\) 一开始，无论 \(isrc(p)\) 值如何，is_rc 的初始值为 \(\text{true}\)，这样，在一开始就能检查左子树是否有答案（见代码）。
该做法的正确性：答案有两种情况：

• 在 \(p\) 的左子树上；
• 在 \(p\) 的某个祖先的左子树上。

易证这些数能覆盖所有 \(<val\) 的数。
若答案在 \(p\) 的左子树上，那么一开始即已经检查到。
否则，如果当前的点为 \(x\)，那么若 \(isrc(x) = 0\)，那么往上跳。这样除了 \(p\) 左子树上的数就没有 \(< val\) 的数了。若 \(isrc(x) = 1\)，那么答案在左子树（因为 \(< val\) 的数只在 \(x\) 的左子树上）。还有一种特殊情况，答案为某个祖先，需要判断一下。
特别的，无需担心左子树有结点但全被打标的情况，因为此时左子树的 \(\beta' = 1 \ge \beta\)。

    int tans;
    void Dfs_Pre(int x)
    {
        if(tree[x].rc != -1)
            Dfs_Pre(tree[x].rc);
        if(tans != -1)
            return ;
        if(!tree[x].del)
        {
            tans = tree[x].val;
            return ;
        }
        if(tree[x].lc != -1)
            Dfs_Pre(tree[x].lc);
    }
    int Find_Pre(int x, int val, bool is_rc)
    {
        tans = -1;
        if(!is_rc) // is_rc = 0，向上跳
            return Find_Pre(tree[x].fa, val, (tree[x].fa != -1)?(tree[tree[x].fa].rc == x):false);
        if(!tree[x].del && tree[x].val < val) // 答案为某个祖先
            return tree[x].val;
        if(tree[x].lc != -1) // is_rc = 1 且左子树不为空
        {
            Dfs_Pre(tree[x].lc);
            return tans;
        }
        return Find_Pre(tree[x].fa, val, (tree[x].fa != -1)?(tree[tree[x].fa].rc == x):false); // 继续往上
    }

找后继代码 Dfs_Nxt 和 Find_Nxt 几乎与找前驱类似，原理也类似，相当于 Dfs_Pre 函数和 Find_Pre 函数全部反过来。

    void Dfs_Nxt(int x)
    {
        if(tree[x].lc != -1)
            Dfs_Nxt(tree[x].lc);
        if(tans != -1)
            return ;
        if(!tree[x].del)
        {
            tans = tree[x].val;
            return ;
        }
        if(tree[x].rc != -1)
            Dfs_Nxt(tree[x].rc);
    }
    int Find_Nxt(int x, int val, bool is_lc)
    {
        tans = -1;
        if(!is_lc)
            return Find_Nxt(tree[x].fa, val, (tree[x].fa != -1)?(tree[tree[x].fa].lc == x):false);
        if(!tree[x].del && tree[x].val > val)
            return tree[x].val;
        if(tree[x].rc != -1)
        {
            Dfs_Nxt(tree[x].rc);
            return tans;
        }
        return Find_Nxt(tree[x].fa, val, (tree[x].fa != -1)?(tree[tree[x].fa].lc == x):false);
    }

2.3 替罪羊树完整代码

抽象的 \(258\) 行。

/**                                                                                        {        
 * problem: 替罪羊树        
 * site: \	
 * author: _Z_F_R_
 * date: 2023-10-05 14:26:30    
 **/       
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
const double Alpha = 0.75, Beta = 0.3;
int seqsize;
struct tSeq
{
    int val, cnt;
}tseq[N << 1];
struct Scapegoat_Tree
{
    struct tNode
    {
        int lc, rc, fa, val, cnt, nodesize, avsize, numsize;
        bool del;
    }tree[N << 1];
    int root, used, inst;
    Scapegoat_Tree() { root = -1; }
    stack<int>mem;
    int newmem()
    {
        if(inst > 0)
        {
            inst--;
            int top = mem.top();
			mem.pop();
			return top;
        }
        return ++used;
    }
    void Add_Node(int nid, int val, int fa)
    {
        tree[nid].fa = fa, tree[nid].lc = tree[nid].rc = -1, tree[nid].val = val;
        tree[nid].cnt = tree[nid].nodesize = tree[nid].avsize = tree[nid].numsize = 1, tree[nid].del = false;
    }
    int Find_Pos(int x, int val)
    {
        if(val < tree[x].val && tree[x].lc != -1)
            return Find_Pos(tree[x].lc, val);
        if(val > tree[x].val && tree[x].rc != -1)
            return Find_Pos(tree[x].rc, val);
        return x;
    }
    void Update(int x, int nodeadd, int avadd, int numadd)
    {
        if(x == -1)
            return ;
        tree[x].nodesize += nodeadd, tree[x].avsize += avadd, tree[x].numsize += numadd;
        Update(tree[x].fa, nodeadd, avadd, numadd);
    }
    void Dfs(int x)
    {
        if(x == -1)
            return;
        Dfs(tree[x].lc);
        if(!tree[x].del)
            tseq[++seqsize].val = tree[x].val, tseq[seqsize].cnt = tree[x].cnt, mem.push(x), inst++;
        Dfs(tree[x].rc);
    }
    int ReAdd(int l, int r, int fa)
    {
        if(l > r)
            return -1;
        int mid = (l + r) >> 1;
        int nid = newmem();
        tree[nid].fa = fa;
        tree[nid].cnt = tseq[mid].cnt;
        tree[nid].val = tseq[mid].val;
        tree[nid].lc = ReAdd(l, mid - 1, nid);
        tree[nid].rc = ReAdd(mid + 1, r, nid);
        tree[nid].numsize = tree[tree[nid].lc].numsize + tree[tree[nid].rc].numsize + tseq[mid].cnt;
        tree[nid].nodesize = tree[nid].avsize = r - l + 1;
        return nid;
    }
    void ReBuild(int x)
    {
        seqsize = 0;
        Dfs(x);
        if(x == root)
            root = ReAdd(1, seqsize, -1);
        else
        {
            Update(x, tree[x].avsize - tree[x].nodesize, 0, 0);
            if(tree[tree[x].fa].lc == x)
                tree[tree[x].fa].lc = ReAdd(1, seqsize, tree[x].fa);
            else
                tree[tree[x].fa].rc = ReAdd(1, seqsize, tree[x].fa);
        }
    }
    void Find_ReBuild(int x, int val)
    {
        if(double(max(tree[tree[x].lc].nodesize, tree[tree[x].rc].nodesize)) > (tree[x].nodesize - 1) * Alpha || double(tree[x].nodesize - tree[x].avsize) > tree[x].nodesize * Beta)
        {
            ReBuild(x);
            return ;
        }
        if(tree[x].val != val)
            Find_ReBuild((tree[x].val > val)?tree[x].lc:tree[x].rc, val);
    }
    void Add(int val)
    {
        if(root == -1)
        {
            Add_Node(root = newmem(), val, -1);
            return ;
        }
        int p = Find_Pos(root, val);
        if(tree[p].val == val)
        {
            tree[p].cnt++;
            if(tree[p].del)
                tree[p].del = false, Update(p, 0, 1, 1);
            else
                Update(p, 0, 0, 1);
        }
        else if(tree[p].val > val)
            Add_Node(tree[p].lc = newmem(), val, p), Update(p, 1, 1, 1);
        else
            Add_Node(tree[p].rc = newmem(), val, p), Update(p, 1, 1, 1);
		Find_ReBuild(root, val);
    }
    void Del(int val)
    {
        int p = Find_Pos(root, val);
        tree[p].cnt--;
        if(!tree[p].cnt)
            tree[p].del = true, Update(p, 0, -1, -1);
        else
            Update(p, 0, 0, -1);
        Find_ReBuild(root, val);
    }
    int Find_Rank(int val)
    {
        int x = root, ans = 0;
        while(tree[x].val != val)
        {
            if(x == -1)
                return ans + 1;
            if(val < tree[x].val)
                x = tree[x].lc;
            else
                ans += tree[tree[x].lc].numsize + tree[x].cnt, x = tree[x].rc;
        }
        if(tree[x].lc != -1)
            ans += tree[tree[x].lc].numsize;
        return ans + 1;
    }
    int Find_Num(int rank)
    {
        int x = root, rrank = rank;
        while(true)
        {
            if(rrank <= tree[tree[x].lc].numsize)
                x = tree[x].lc;
            else
            {
                rrank -= tree[tree[x].lc].numsize;
                if(rrank <= tree[x].cnt)
                    return tree[x].val;
                rrank -= tree[x].cnt, x = tree[x].rc;
            }
        }
    }
    int tans;
    void Dfs_Pre(int x)
    {
        if(tree[x].rc != -1)
            Dfs_Pre(tree[x].rc);
        if(tans != -1)
            return ;
        if(!tree[x].del)
        {
            tans = tree[x].val;
            return ;
        }
        if(tree[x].lc != -1)
            Dfs_Pre(tree[x].lc);
    }
    int Find_Pre(int x, int val, bool is_rc)
    {
        tans = -1;
        if(!is_rc)
            return Find_Pre(tree[x].fa, val, (tree[x].fa != -1)?(tree[tree[x].fa].rc == x):false);
        if(!tree[x].del && tree[x].val < val)
            return tree[x].val;
        if(tree[x].lc != -1)
        {
            Dfs_Pre(tree[x].lc);
            return tans;
        }
        return Find_Pre(tree[x].fa, val, (tree[x].fa != -1)?(tree[tree[x].fa].rc == x):false);
    }
    void Dfs_Nxt(int x)
    {
        if(tree[x].lc != -1)
            Dfs_Nxt(tree[x].lc);
        if(tans != -1)
            return ;
        if(!tree[x].del)
        {
            tans = tree[x].val;
            return ;
        }
        if(tree[x].rc != -1)
            Dfs_Nxt(tree[x].rc);
    }
    int Find_Nxt(int x, int val, bool is_lc)
    {
        tans = -1;
        if(!is_lc)
            return Find_Nxt(tree[x].fa, val, (tree[x].fa != -1)?(tree[tree[x].fa].lc == x):false);
        if(!tree[x].del && tree[x].val > val)
            return tree[x].val;
        if(tree[x].rc != -1)
        {
            Dfs_Nxt(tree[x].rc);
            return tans;
        }
        return Find_Nxt(tree[x].fa, val, (tree[x].fa != -1)?(tree[tree[x].fa].lc == x):false);
    }
    void Print()
    {
		printf("%d\n", root);
        int i;
        for(i = 1; i <= used; i++)
            printf("%d : [%d] fa : %d lc : %d rc : %d cnt : %d val : %d size : [%d, %d, %d]\n", i, tree[i].del, tree[i].fa, tree[i].lc, tree[i].rc, tree[i].cnt, tree[i].val, tree[i].nodesize, tree[i].avsize, tree[i].numsize);
    }
}bst;

int main()
{
	int n;
    scanf("%d", &n);
    while(n--)
    {
        int op, val;
        scanf("%d %d", &op, &val);
        if(op == 1)
            bst.Add(val);
        else if(op == 2)
            bst.Del(val);
        else if(op == 3)
            printf("%d\n", bst.Find_Rank(val));
        else if(op == 4)
            printf("%d\n", bst.Find_Num(val));
        else if(op == 5)
            printf("%d\n", bst.Find_Pre(bst.Find_Pos(bst.root, val), val, true));
        else
            printf("%d\n", bst.Find_Nxt(bst.Find_Pos(bst.root, val), val, true));
    }
}
# 3 Treap
~~今天 lxl 到信友队来讲 ds，想起来还有这篇文章，遂来补。~~
## 3.1 Treap 的维护
众所周知 Treap = Tree + heap，所以我们每个结点随机赋一个权值 $rk$，在满足上述二叉搜索树的性质的同时，保证父节点的 $rk$ 比其子结点的 $rk$ 大（或小）。
感性理解一下，这样建出来的的树一般深度不会太高。
传统 Treap 的维护方法是旋转，但是 FHQ Treap 大法好！
## 3.2 FHQ Treap 的基本操作
### 3.2.1 FHQ Treap 的结点信息
`ls`、`rs`：左右儿子。不存在则为 $0$。
`val`、`rk`、`cnt`：结点的值、权值及个数。
`siz`：子树大小。
`tot`：当前结点数。
```cpp
	int ls[N], rs[N], siz[N], cnt[N], val[N], rk[N];
	
int tot, root;

PushUp：更新 siz。

	void PushUp(int u) {
		siz[u] = siz[ls[u]] + siz[rs[u]] + cnt[u];
	}

3.2.2 FHQ Treap 的分裂

3.2.2.1 按值分裂

给定参数 \(k\)，将平衡树分成 \(\alpha\) 与 \(\beta\) 两颗平衡树，使得 \(\alpha\) 中结点的值小于等于 \(k\)，\(\beta\) 中结点的值大于 \(k\)。
考虑函数 Split_Num(u, k)，返回 \(\alpha\) 与 \(\beta\)，对于结点 \(u\)：

• 若 \(val_u \le k\)，则 \(u \in \alpha\)，递归解决 Split_Num(rs[u], k)，返回了 \(\alpha'\) 与 \(\beta'\)，其中 \(\alpha'\) 接到 \(u\) 的右子树，此时以 \(u\) 为根的子树成为返回的 \(\alpha\)，让 \(\beta \gets \beta'\) 并返回。
• 若 \(val_u > k\)，则 \(u \in \beta\)，递归解决 Split_Num(ls[u], k)，返回了 \(\alpha'\) 与 \(\beta'\)，其中 \(\beta'\) 接到 \(u\) 的左子树，此时以 \(u\) 为根的子树成为返回的 \(\beta\)，让 \(\alpha \gets \alpha'\) 并返回。

最后对 \(u\) 结点进行更新。

	Double Split_Num(int u, int num) { // Double 相当于 pair<int, int>，返回分裂后的根结点
		if(!u) { // 被分裂子树为空，返回 {0, 0}
			return {0, 0};
		}
		if(val[u] <= num) { // 同上 val_u <= k
			Double p = Split_Num(rs[u], num);
			rs[u] = p.l;
			PushUp(u);
			return {u, p.r};
		}
		else { // 同上 val_u > k
			Double p = Split_Num(ls[u], num);
			ls[u] = p.r;
			PushUp(u);
			return {p.l, u};
		}
	}

3.2.2.2 按排名分裂

给定参数 \(k\)，将平衡树分成 \(\alpha\)、\(\beta\) 和 \(\gamma\) 三颗平衡树，使得 \(\alpha\) 中存储的所有数的排名小于 \(k\)，\(\beta\) 为一个结点 \(u\)，存储的 \(cnt_u\) 个树中有一个数排名恰好为 \(k\)，\(\gamma\) 中存储的所有数的排名大于 \(k\)。
考虑函数 Split_Rk(u, k)，返回 \(\alpha\)、\(\beta\) 与 \(\gamma\)，对于结点 \(u\)，令左子树大小为 \(x\)：

• 若 \(x \ge k\)，则 \(u \in \gamma\)，递归解决 Split_Rk(ls[u], k)，返回了 \(\alpha'\)、\(\beta'\) 与 \(\gamma'\)，其中 \(\gamma'\) 接到 \(u\) 的左子树，此时以 \(u\) 为根的子树成为返回的 \(\gamma\)，让 \(\alpha \gets \alpha', \beta \gets \beta'\) 并返回。
• 否则，若 \(x + cnt_u \ge k\)，则 \(u \in \beta\)，左子树即为 \(\alpha\)，右子树即为 \(\gamma\)。
• 否则，\(u \in \alpha\)，递归解决 Split_Rk(rs[u], k)，返回了 \(\alpha'\)、\(\beta'\) 与 \(\gamma'\)，其中 \(\alpha'\) 接到 \(u\) 的右子树，此时以 \(u\) 为根的子树成为返回的 \(\alpha\)，让 \(\beta \gets \beta', \gamma \gets \gamma'\) 并返回。

最后对 \(u\) 结点进行更新。

	Triple Split_Rk(int u, int rk) { // Triple 相当于一个 tuple，返回分裂后的根结点
		if(!u) {
			return {0, 0, 0};
		}
		if(siz[ls[u]] >= rk) { // 同上 x >= k
			Triple p = Split_Rk(ls[u], rk);
			ls[u] = p.r;
			PushUp(u);
			return {p.l, p.mid, u};
		}
		else if(siz[ls[u]] + cnt[u] >= rk) { // 同上 x + cnt_u >= k
			Double p = {ls[u], rs[u]};
			ls[u] = rs[u] = 0;
			PushUp(u);
			return {p.l, u, p.r};
		}
		else {
			Triple p = Split_Rk(rs[u], rk - siz[ls[u]] - cnt[u]); // 同上 x + cnt_u < k
			rs[u] = p.l;
			PushUp(u);
			return {u, p.mid, p.r};
		}
	}

参考：
https://blog.csdn.net/a_forever_dream/article/details/81984236