平衡树

简介

平衡树是可以维护 权值信息 的数据结构。平衡树通过对二叉搜索树树高的平衡调整优化插入、删除、修改和查找的复杂度。故而节点其实形成了一个二叉树的形态，通过特定函数支持了查询序列中元素的前驱/后继，排名和特定排名的元素等有关权值的信息。

根据平衡树结构特性，也有维护区间用法。所以平衡树主要有区间平衡树和权值平衡树之分。根据实现不同，平衡树有Treap、Splay、WBLT、SBT、替罪羊树、红黑树等分支。但主流平衡树还是Treap（树堆）和Splay（伸展树）两家。

二叉搜索树

作为平衡树家族的祖宗，BST有其定义带来的特殊性质，为一切平衡树打下了结构基础。

定义

二叉搜索树左子树的点权均小于根节点点权，二叉搜索树右子树的点权均大于根节点点权。且左右子树均为二叉搜索树。

性质

我们发现，给定目标值，从根节点出发一路与目标值进行比较，一定能走到目标位置。且中序遍历得到的是一个有序序列，最小最大值分处左右链顶点。给定排名，从根节点出发一路与左子树大小比较，一定能找到目标权值。反之可以确定某个值的排名。

问题

不难发现上述操作会走过树的某条链，理想情况下每条链长度为 \(\log n\)，但树变成链时随随便便卡成 \(O(n)\) 不成问题。于是为了保证 \(O(\log n)\) 的复杂度，平衡树应运而生。何谓平衡？将每个节点左右子树高度差控制在 \(1\) 以内，调整后的二叉搜索树就成了平衡二叉树。

解法

观察到二叉搜索树的这样一种性质：

这样旋转过后仍然具有二叉搜索树性质，但节点相对位置和父子关系发生了改变。我们称从左到右的变换是“右旋”（zig），从右到左的变换是“左旋”（zag）。因为这种旋转操作（rotate）的存在，平衡树的故事由此展开。

笛卡尔树

结构

笛卡尔树是一种二叉树，每一个结点由一个键值二元组 \((k,w)\) 构成。要求 \(k\) 满足二叉搜索树的性质，而 \(w\) 满足堆的性质。

int ls[N], rs[N], stk[N], top;

性质

与善变的二叉平衡树不同，如果笛卡尔树的 \(k,w\) 键值确定，且 \(k、w\) 互不相同，那么这个笛卡尔树的结构是唯一的。

操作

笛卡尔树贵在其建树的思想：在把数组元素值当作键值 \(w\)，而把数组下标当作键值 \(k\) 时，可以简单地使用单调栈不断加入新点，维护堆的性质。并在不满足单调性时回退至第一个不合法的栈位置，将其置为新点左儿子，并将新点入栈。否则将新点置为栈顶的右儿子。

void build() {
    for (int i = 1; i <= n; i++) {
        int k = top;
        while (k > 0 && h[stk[k]] > h[i]) k--;
        if (k) rs[stk[k]] = i;  // rs代表笛卡尔树每个节点的右儿子
        if (k < top) ls[i] = stk[k + 1];  // ls代表笛卡尔树每个节点的左儿子
        stk[++k] = i;
        top = k;
    }
}

而 Treap 是一类特殊的笛卡尔树。

Treap（树堆）

Treap 作为特殊的笛卡尔树，有分无旋、有旋式 Treap。旋转 Treap 正是通过 zig、zag 操作改变父子节点位置做到维护堆性质。而无旋 Treap 则另辟蹊径，使用了合并（merge）、分裂（split）实现。更有 FHQ-Treap 做到平衡树中绝无仅有的可持久化。

结构

既然本质是二叉树，记录根节点和每个点的左右儿子以及子树大小、点权、键值和副点个数（同一权值重复出现的情况）即可。为了便于无旋 Treap 分裂出的子树存储，再开几个临时根节点即可。

int ls[N], rs[N], key[N], val[N], cnt[N], sz[N];
int rt, x, y, z, tot;

虽然话是这么说，FHQ-Treap 的主流写法一般偷懒地直接重复加点，而不记录副点个数。

性质

Treap 以点权 \(val\) 作为键值 \(k\)，满足二叉搜索树性质。随机出的一个值作为键值 \(w\)。保证树高期望在 \(\log n\)。树堆是树如其名，其核心思想是搜索树+堆：其一大特色就是插入、删除等操作都要再最后维护堆的性质。

权值操作

无旋 Treap

先学完可并堆的合并操作和线段树的合并、分裂操作后再看无旋 Treap 尤为亲切。其核心操作就是合并、分裂。掌握这两个技能，就能完成一系列操作。并且对于正整数域权值，有良好性质：按目标值 \(val\) 分裂后再按 \(val-1\) 分裂就得到了单为 \(val\) 值的一棵子树。但是谨记分裂后要重新合并！

基础

盖高楼自然先从烧砖头开始。

int create(int x) {
  	int p = ++ tot;
  	val[p] = x;
  	key[p] = rand(); //Treap之精华
  	sz[p] = 1;
  	return p;
}
void maintain(int p) {sz[p] = sz[ls[p]] + sz[rs[p]] + 1;}

分裂

有两种分裂方式：按值分裂和按排名分裂。

这里先讲按值分裂。与线段树分裂异曲同工，在原树上分裂出节点权值均小于等于 \(val\) 的子树，以 \(x\) 为根，和大于 \(val\) 的子树，以 \(y\) 为根。过程就是不断分讨：当前结点权值小于等于 \(val\) 就将其及左子树一并划给 \(x\) ，递归分裂右子树中属于 \(x\) 的一部分。反之将其及右子树分给 \(y\) ，递归分裂左子树中属于 \(y\) 的一部分。这与线段树分裂中不断递归交集区间分裂思想不谋而和。

void split(int &x, int &y, int p, int v) {
	if (!p) {x = y = 0; return;}
	if (val[p] <= v) {
		x = p; split(rs[x], y, rs[p], v);
	}
	else {
		y = p; split(x, ls[y], ls[p], v);
	}
	maintain(p);
}

合并

相似地，几种数据结构的合并都相差无几。但是注意在 Treap 中需要在上方的点键值更小，就像左偏树要求左儿子 \(dis\) 更大一样。并且，两个 Treap 能够合并的前提是左边的 Treap \(x\) 中最大值应小于右边 Treap \(y\) 中最小值。不然因为不能旋转，会无法满足二叉搜索树性质。

int merge(int x, int y) {
	if (!x || !y) return x | y;
	if (key[x] < key[y]) {
		rs[x] = merge(rs[x], y);
		maintain(x);
		return x;
	}
	else {
		ls[y] = merge(x, ls[y]);
		maintain(y);
		return y;
	}
}

插入

不难发现，我们可以按插入的值 \(val\) 分裂 Treap，掰成两块 \(x、y\) 后先将 \(x\) 与 \(tot\) 拼回去，再拼回 \(y\)，大功告成！

void ins(int v) {
    split(x, y, rt, v);
    rt = merge(merge(x, create(v)), y);
}

删除

同理，我们可以按删除的值 \(val\) 分裂 Treap，掰成两块 \(x、z\) 后再从 \(x\) 中分出等于 \(val\) 的节点组成的 Treap \(y\)，单独删掉 \(y\) 的根节点的思路类比左偏树，合并其左右子树即可。最后把三块拼好，大功告成！

void del(int v) {
    split(x, z, rt, v);
    split(x, y, x, a-1);
    y = merge(ls[y], rs[y]);
    rt = merge(merge(x, y), z);
}

查询排名对应权值

使用二叉搜索树的方法进行模拟，找到目标点。

int kth(int p, int k) {
	while (1) {
		if (k <= sz[ls[p]]) p = ls[p];
		else if (k == sz[ls[p]] + 1) return p;
		else k -= sz[ls[p]]+1, p = rs[p];
	}
}

查询权值对应前驱/后继/排名

实现类似，先按 \(val-1\) 分裂的话比其小的点就都在 \(x\) 里了，排名就是sz[x]+1，前驱就是 \(x\) 中第 sz[x] 小的（就是最大的），按 \(val\) 分裂的话比其大的点就都在 \(y\) 里了，后继就是 \(y\) 中最小的。

void rank(int v) {
	split(x, y, rt, v-1);
	printf("%d\n", sz[x]+1);
	rt = merge(x, y);
}
void pre(int v) {
    split(x, y, rt, v-1);
    printf("%d\n", val[kth(x, sz[x])]);
    rt = merge(x, y);
}
void nxt(int v) {
    split(x, y, rt, v);
    printf("%d\n", val[kth(y, 1)]);
    rt = merge(x, y);
}

有旋 Treap

有旋Treap在FHQ-Treap面前就是依托。更有不得不学的同为将旋转玩出花的Splay打底，这有旋Treap不学也罢！

struct Node {
    int l, r;
    int key, val;
    int cnt, size;
} tr[N];
int root, idx;
void pushup(int p) {
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;
}
int creat(int key) {
    int p = ++idx  ;
    tr[p].key = key;
    tr[p].val = rand();
    tr[p].cnt = tr[p].size = 1;
    return p;
}
void zig(int &p) {
    int q = tr[p].l;
    tr[p].l = tr[q].r;
    tr[q].r = p;
    tr[q].size = tr[p].size;
    pushup(p);
    p = q;
}
void zag(int &p) {
    int q = tr[p].r;
    tr[p].r = tr[q].l;
    tr[q].l = p;
    tr[q].size = tr[p].size;
    pushup(p);
    p = q;
}
void build() {
    creat(INF), creat(-INF);
    root = 1; tr[1].l = 2;
    pushup(1);
    if (tr[1].val < tr[2].val) zig(root);
}
void insert(int &p, int key) {
    if (!p) p = creat(key);
    else if (tr[p].key > key) {
        insert(tr[p].l, key);
        if (tr[p].val < tr[tr[p].l].val) zig(p);
    }
    else if (tr[p].key < key) {
        insert(tr[p].r, key);
        if (tr[p].val < tr[tr[p].r].val) zag(p);
    }
    else tr[p].cnt ++ ;
    pushup(p);
}
void removed(int &p, int key) {
    if (!p) return;
    if (tr[p].key > key) removed(tr[p].l, key);
    else if (tr[p].key < key) removed(tr[p].r, key);
    else {
        if (tr[p].cnt > 1) tr[p].cnt -- ;
        else if (tr[p].l || tr[p].r) {
            if (!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val) {
                zig(p);
                removed(tr[p].r, key);
            }
            else {
                zag(p);
                removed(tr[p].l, key);
            }
        }
        else p = 0;
    }
    pushup(p);
}
int kth(int p, int key) {
    if (!p) return 0;
    if (tr[p].key == key) return tr[tr[p].l].size + 1;
    if (tr[p].key > key) return kth(tr[p].l, key);
    return tr[tr[p].l].size + tr[p].cnt + kth(tr[p].r, key);
}
int rk(int p, int rank) {
    if (!p) return INF;
    if (tr[tr[p].l].size >= rank) return rk(tr[p].l, rank);
    if (tr[tr[p].l].size + tr[p].cnt >= rank) return tr[p].key;
    return rk(tr[p].r, rank - tr[tr[p].l].size - tr[p].cnt);
}
int pre(int p, int key) {
    if (!p) return -INF;
    if (tr[p].key >= key) return pre(tr[p].l, key);
    return max(tr[p].key, pre(tr[p].r, key));
}
int nxt(int p, int key) {
    if (!p) return INF;
    if (tr[p].key <= key) return nxt(tr[p].r, key);
    return min(tr[p].key, nxt(tr[p].l, key));
}

区间操作（无旋Treap）

编写顺序有些混乱，这一部分放在最后写的

Treap 作为平衡树，依然可以沿用平衡树操作区间的思想。抓住第 \(k\) 大就是区间第 \(k\) 个的性质。

基础

翻转懒标记思想不变。

void pushup(int p) {sz[p] = sz[ls[p]] + sz[rs[p]] + 1;}
void pushdown(int p) {
    if (!tag[p]) return;
    swap(ls[p], rs[p]);
    if (ls[p]) tag[ls[p]] ^= 1;
    if (rs[p]) tag[rs[p]] ^= 1;
    tag[p] = 0;
}

分裂

只有查询区间第 \(k\) 大（序列第 \(k\) 个）的操作得以保留，正中无旋 Treap 下怀。Splay 选择了使用 kth() ，而 Treap 刚好有按排名分裂的操作。

void split(int &x, int &y, int p, int k) {
    if (!p) {x = y = 0; return;}
   	pushdown(p);
    if(sz[ls[p]] < k)
        x = p, split(rs[x], y, rs[p], k-sz[ls[p]]-1);
    else
        y = p, split(x, ls[y], ls[p], k);
    pushup(p);
}

合并

int merge(int x, int y) {
    if (!x || !y) return x | y;
    if (key[x] < key[y]) {
        pushdown(x);
        rs[x] = merge(rs[x], y);
        pushup(x);
        return x;
    }
    else {
        pushdown(y);
        ls[y] = merge(x, ls[y]);
        pushup(y);
        return y;
    }
}

翻转

Splay 通过找“前驱”、“后继”定位目标区间。Treap则可以直接分裂出包含 \([l,n]\) 的子树 \(y\) ，再分裂出仅有 \([l,r]\) 的子树 \(z\)，对 \(z\) 打上标记后合并即可。

void reverse(int l, int r) {
    split(x, y, rt, l-1);
    split(z, y, y, r-l+1);
    tag[z] ^= 1;
    rt = merge(x, merge(z, y));
}

Splay（伸展树）

结构

需要再记录父亲节点。

int fa[N], ch[N][2], cnt[N], sz[N], val[N];
int rt, tot;

trick：使用ch[][2]数组可以方便地使用 \(0、1\) 代表左/右儿子，这样便于判断父子相对位置。

性质

Splay树依然树如其名。其核心操作是伸展操作（splay）：将一个节点通过旋转操作（rotate）调整至根节点以均摊复杂度。所以 Splay 一大特色就是各种操作后的一句 splay。在 splay 时为保证操作合法，我们常使用这个 trick：插入 \(+\infin\) 和 \(-\infin\) 作为哨兵。毫不夸张地说，掌握了 splay 操作，其它操作就是简单的模拟了。

权值操作

基础

对于树的基本处理：维护子树大小和取得父子相对位置。

bool get(int x) {return x == ch[fa[x]][1];}
void maintain(int x) {sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x];}

旋转

具体分析一次旋转步骤（假设需要旋转的节点为 \(x\)，其父亲为 \(y\) 。用chk表示 \(x\) 相对 \(y\) 在左边还是右边。以右旋为例。）

1. 将 \(y\) 的左儿子指向 \(x\) 的右儿子，且 \(x\) 的右儿子父亲指向 \(y\)；
2. 将 \(x\) 的右儿子指向 \(y\)，且 \(y\) 的父亲指向 \(x\)；
3. 如果原来的 \(y\) 还有父亲 \(z\)，那么把 \(z\) 的某个儿子（原来 \(y\) 所在的儿子位置）指向 \(x\)，且 \(x\) 的父亲指向 \(z\)。

void rotate(int x) {
    int y = fa[x], z = fa[y], chk = get(x), w = ch[x][chk ^ 1];
    if (z) ch[z][get(y)] = x; fa[x] = z;
    if (w) fa[w] = y; ch[y][chk] = w;
    ch[x][chk ^ 1] = y; fa[y] = x;
    maintain(y); maintain(x);
}

伸展

splay 分为单旋和双旋。单旋自然就是指一次 zig 或 zag 操作后就能旋转至目标节点（默认为根）。双旋则对应两种情况：

• \(x\) 及其父亲 \(y\)、爷爷 \(z\) 排列成 “ / ” 或 “ \ ” 形的情况，对 \(x\) 执行两次单旋操作。
• \(x\) 及其父亲 \(y\)、爷爷 \(z\) 排列成 “ < ” 或 “ > ” 形的情况，先对 \(y\) 执行一次单旋，再对 \(x\) 执行一次单旋。

void splay(int x, int goal = 0) {
    for (int f = fa[x]; f = fa[x], f != goal; rotate(x))
        if (fa[f] != goal) rotate(get(x) == get(f) ? f : x);
    if (!goal) rt = x;
}

插入

应用二叉搜索树性质，从根节点找到当前权值应在位置。依情况更新 cnt[] 信息或新建节点。

void ins(int x) {
    int cur = rt, f = 0;
    while (cur && val[cur] != x) {
        f = cur;
        cur = ch[cur][x > val[cur]];
    }
    if (cur) cnt[cur] ++; //如果有相等的，cnt++
    else {
        cur = ++ tot;
        if (f) ch[f][x > val[f]] = cur;
        val[cur] = x; fa[cur] = f;
        cnt[cur] = sz[cur] = 1;
    } //没有则新开点
    splay(cur);
}

删除

同插入相似，找到当前权值应在位置。依情况更新 cnt[] 信息或删除节点。但是重复这种方法略显无聊。结合下面的前驱/后继操作，我们可以有如下思路：将前驱转至根，后继接到前驱，这样后继成为前驱右儿子后左儿子只能包含目标节点，直接对其操作即可。

 void del(int k) {
     int pre = find(k, 0), nxt = find(k, 1);
     splay(pre);
     splay(nxt, pre);
     int cur = ch[ne][0];
     if (cnt[cur] > 1) cnt[cur] --, splay(cur);
     else ch[nxt][0] = 0;
 }

查询权值对应前驱 / 后继 / 排名

这三个操作过程相似，故干脆压缩到一起操作。同样的，先从根节点找到当前权值应在位置。注意，给出的权值不一定在平衡树中，可能 只能找到 近似的值（前驱或后继），所以使用这种方法求排名时需特别注意。不然会被hack！

譬如，在这棵平衡树中，我们试图从根节点开始找到 \(7\) 应在的位置。可是走到 \(6\) 发现无路可走时，我们只能返回这个前驱值所在位置。同理，在我们试图找到 \(3\) 应在的位置时会遇到同样的麻烦，只能返回 \(4\) 这个后继值所在位置。

那么，在模拟过程结束后，我们对找到的值先执行 splay。接下来我们分讨：

对于找前驱/后继操作，如果根节点本身就是前驱/后继就能直接返回。不然依据二叉搜索树性质找到相应的左（右）子树中的最大（小）值——根节点左（右）儿子的右（左）链顶点。

对于求排名操作，如果根节点本身就是后继/自身就能直接返回左子树大小（已有哨兵贡献+1），否则还应加上根节点的 cnt[] 值。

int rk(int x) { //找到相等节点或前驱/后继节点 
    int cur = rt;
    if (!cur) return; //特判树为空
    while (ch[cur][x > val[cur]] && x != val[cur])
        cur = ch[cur][x > val[cur]];
    splay(cur); return sz[ch[rt][0]] + (val[rt] < x ? cnt[rt] : 0);
}
int find(int x, int f) { //0前驱，1后继 
    rk(x);
    if ((val[rt] > x && f) || (val[rt] < x && !f)) return rt;
    int cur = ch[rt][f];
    while (ch[cur][f ^ 1]) cur = ch[cur][f ^ 1];
    splay(cur); return cur;
}

查询排名对应权值

设 \(k\)​ 为剩余排名。

• 如果左子树非空且剩余排名 \(k\) 不大于左子树的大小，那么向左子树查找。
• 否则将 \(k\) 减去左子树的和根的大小。如果此时 \(k\) 的值小于等于 \(0\)，则返回根节点的权值，否则继续向右子树查找。

int kth(int k) {
    int cur = rt;
    if (sz[rt] < k) return 0; //比总数多的排名不存在
    while (true) {
        if (ch[cur][0] && k <= sz[ch[cur][0]])
            cur = ch[cur][0];
        else {
            k -= cnt[cur] + sz[ch[cur][0]];
            if (k <= 0) {
                splay(cur);
                return val[cur];
            }   
            cur = ch[cur][1];
        }
    }
}

区间操作

区别

线段树能改成维护权值，平衡树也能改成维护区间。此时的val[]数组只是没用的附带品，纯纯用于输出罢了。那么与权值有关的 find()、rk()等函数都无用武之地。同时不存在出现副点的情况，不需要cnt[]数组（每个点 cnt 都是 1）。

此时的平衡树真正重要的是其结构特性：中序遍历 能得到 当前序列 ——将下标构建得满足二叉搜索树特性不就便于维护区间了吗。维护一个可以不断翻转的区间还会用到类似线段树的翻转懒标记与其对应的下传。此时懒标记意即该点子树是否需要翻转，因为两次翻转可以抵消，简单异或维护即可。

根据树的中序遍历的结论不难发现需要翻转时将标记下放到两儿子后交换左右儿子，不断递归这一过程就能实现中序遍历的彻底翻转，可以画个图验证规律。同样的，将原始序列前后加一个哨兵。所以注意其后的操作需要将给出的 \(k\) 加一抵消左哨兵的贡献。

int ori[N], tag[N];

基础

bool get(int x) {return x == ch[fa[x]][1];}
void pushup(int x) {if (x) sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;}
void pushdown(int x) {
    if (x && tag[x]) {
        tag[x] = 0;
        tag[ch[x][0]] ^= 1;
        tag[ch[x][1]] ^= 1;
        swap(ch[x][0], ch[x][1]);
    }
}

旋转

类比线段树修改时需要下放标记，这里同理。一定注意顺序，比如先下放父亲再下放儿子、下放标记完成后再判断chk。这里的处理细节需要注意，不然在文艺平衡树中有 kth() 给你兜底，其它题就不一定了：关于splay的下放标记操作、求助关于splay函数的标记下传。

void rotate(int x) {
    int y = fa[x], z = fa[y];
    pushdown(y); pushdown(x);
    int chk = get(x), w = ch[x][chk^1];
    fa[x] = z; if (z) ch[z][get(y)] = x;
    ch[y][chk] = w; if (w) fa[w] = y;
    ch[x][chk ^ 1] = y; fa[y] = x;
    pushup(y); pushup(x);
}

伸展

void splay(int x, int goal = 0) {
    for (int f = fa[x]; f = fa[x], f != goal; rotate(x)) {
        if (fa[f] != goal) rotate(get(f) == get(x) ? f : x);
    }
    if (!goal) rt = x;
}

建树

对于给定的序列，类比线段树建树，从中点将序列拎起来就足够平衡了。

int build(int l, int r, int f) {
    if (l > r) {return 0;}
    int mid = (l + r) >> 1;
    int idx = ++ tot;
    fa[idx] = f; sz[idx] = 1;
    val[idx] = ori[mid];
    ch[idx][0] = build(l, mid - 1, idx);
    ch[idx][1] = build(mid + 1, r, idx);
    pushup(idx);
    return idx;
}

按排名找点

我们依然能通过kth()函数找到序列第 \(k\) 个的元素。类比线段树询问时需要下放标记，这里同理。

 int kth(int k) {
     int pos = rt;
     while (1) {
         pushdown(pos);
         if (k <= sz[ch[pos][0]]) {
             pos = ch[pos][0];
         }
         else {
             k -= sz[ch[pos][0]] + 1;
             if (k <= 0) {return pos;}
             pos = ch[pos][1]; 
         }
     }
 }

翻转

这是区间平衡树的重头戏，类比权值平衡树中删除点的思想，我们找到需要翻转的区间 \([l,r]\) 中 \(l\) 的“前驱”——此前驱非彼前驱，这里的前驱指序列中 \(l\) 前的点 \(kth(l-1)\)，再找到 \(r\) 的“后继”——指序列中 \(r\) 后的点 \(kth(r+1)\)。并先后 splay 上去。给夹在中间的子树根节点打上标记即可。

 void reverse(int l, int r) {
     int pre = kth(l-1), nxt = kth(r+1);
     splay(pre);
     splay(nxt, pre);
     int pos = ch[rt][1];
     pos = ch[pos][0];
     tag[pos] ^= 1;
 }

输出

依据区间操作的根本——中序遍历及其在平衡树中的性质，中序遍历即可。

void dfs(int pos) {
    pushdown(pos);
    if (ch[pos][0]) dfs(ch[pos][0]);
    if (-INF < val[pos] && val[pos] < INF) printf("%d ", val[pos]);
    if (ch[pos][1]) dfs(ch[pos][1]);
}