学习笔记 ---- 平衡树 总结
文章目录
- 平衡树的含义
- 二叉搜索树
- t r e a p treap treap
- S p l a y Splay Splay（延伸树）
- 优化思想
- S p l a y Splay Splay 的定义
- 核心操作
- 文艺平衡树（序列操作）
- 练习题
- 平衡树维护序列
- 平衡树维护数集
- F H Q t r e a p FHQ \ treap FHQ treap（无旋 t r e a p treap treap）
- 简介
- 核心操作
- 定义
- 分裂
- 合并
- 基本操作
- 文艺平衡树（序列操作）
- 平衡树的有交并
- 练习题
平衡树的含义
平衡树是一种特殊的 二叉查找树（Binary Search Tree, BST），其重要目的是在保持二叉查找树的基本特性的基础上，通过额外的约束条件确保 树的高度尽可能均衡。从而保证在插入，删除，修改和查找等操作保持较高的性能。
平衡树 与 线段树 对比：
优点：
- 文艺平衡树 能够支持在序列中 插入 一个元素或一段区间。序列线段树 无法做到。
- 文艺平衡树 可以支持 区间翻转，线段树无法做到。
缺点：
- 码量大，细节比较多。
- 仅仅维护 集合，不维护 下标 的平衡树一般可以用 值域线段树 代替。
二叉搜索树 是学习平衡树的基础，因此我们先来学习二叉搜索树。
二叉搜索树
二叉搜索树是 以某一关键字排序 的二叉树。满足左儿子都比根小，右儿子都比根大，同时左右子树都是二叉搜索树。二叉搜索树的中序遍历就是集合内的元素按照关键字排序后的结果。下面以 数值 为关键字的二叉搜索树为例说明。
如图，这就是一棵二叉搜索树的形态：
二叉搜索树支持以下操作：
插入节点
假设我们要插入一个数 x x x，就不断比较它和根的大小关系。（假设没有相同的元素）
-
比根小，递归左子树。
-
比根大，递归右子树。
-
递归到一个空结点，插入。
删除节点 -
这个点是叶子，直接删除即可。
-
这个点只有一个儿子，删去这个点，让它儿子的父亲指向它的父亲。
-
有两个儿子。那么首先递归到右子树，然后一直往左递归找到叶子，交换叶子和这个节点后把叶子删掉。比如要删 7 7 7：
找到 8 8 8 之后交换 7 , 8 7, 8 7,8 再把 7 7 7 删掉。
这样做是对的原因是：找到的叶子相当于是删除节点的 后继。交换这两个节点后再把它删去不会影响别的节点的 中序遍历顺序。
查询 x x x 的排名
不断比较 x x x 与当前根的大小关系直到递归到空结点。
- x x x 大于当前根，排名加上左子树的元素个数 + 1 +1 +1，往右子树递归。
- 否则往左子树递归。
查询第 x x x 大
不断比较 x x x 与当前根的左子树中元素个数的关系。
- x x x 等于左子树大小 + 1 +1 +1，答案就是当前根。
- x x x 小于等于左子树大小，往左子树递归。
- x x x 大于左子树大小 + 1 +1 +1，往右子树递归。
查询
x
x
x 的前驱 / 查询
x
x
x 的后继
与上面方法类似。
或者可以调用上面两个函数完成。
二叉搜索树支持的操作很多，但缺点是复杂度不稳定。
当搜索树退化成一条 链 时，单次操作的复杂度就达到了
O
(
n
)
O(n)
O(n) 量级。
而不同的平衡树就是通过不同的方法去 平衡树高 以保证复杂度。
下面介绍三种常见平衡树。
t r e a p treap treap
首先我们需要知道：
t
r
e
a
p
=
t
r
e
e
+
h
e
a
p
treap = tree + heap
treap=tree+heap。
其中
t
r
e
e
tree
tree 代表二叉搜索树，
h
e
a
p
heap
heap 代表堆。相当于是二者的结合。
t
r
e
a
p
treap
treap 无法支持序列操作，只能够维护集合。
t
r
e
a
p
treap
treap 支持的操作：插入一个数，删掉一个数，查询集合第
k
k
k 大，查询一个数
x
x
x 在集合中的排名，求数
x
x
x 的 前驱 和 后继。
t r e a p treap treap 的核心思想是 利用二叉搜索树的性质完成各种操作，利用堆的性质平衡树高以优化复杂度。
首先需要学习 t r e a p treap treap 的核心操作： r o t a t e rotate rotate 函数。
把右儿子向上翻转称作 左旋，左儿子向上翻转称作 右旋。
口诀：左旋拎右左连右，右旋拎左右连左。
r
o
t
a
t
e
rotate
rotate 可以用来 在不改变二叉搜索树排序性质的基础上，将一个点旋转到它父亲的位置。
比如下图：
要把
6
6
6 转到
4
4
4 的位置：
不难发现这样操作对于二叉搜索树的中序遍历是没有影响的，因此不会改变二叉搜索树的性质。
然后 t r e a p treap treap 的具体做法就是每次插入一个节点时 给这个节点随机一个权重 w w w。我们刚插入时这个点一定是叶子，然后每次跟它父亲的权重比较，如果它更大就把它旋转到父亲的位置。相当于同时维护了一个 大根堆。
别的操作不用改变。这样树高可被优化到
log
n
\log n
logn，单次操作复杂度为
O
(
log
n
)
O(\log n)
O(logn)。
代码就不放了，因为也不太常用。
可以借鉴这篇博客。
S p l a y Splay Splay（延伸树）
S p l a y Splay Splay 是一种比较特殊的平衡树，它不需要向别的平衡树一样将树高维持在 l o g log log，并且在操作过程中树高可能达到 O ( n ) O(n) O(n) 量级。但是通过 均摊 可将单次复杂度均摊到 log \log log 级别，并且相对于其它平衡树而言较快。
发明者是非常 n b nb nb 的 T a r j a n Tarjan Tarjan 神仙。
优化思想
s p l a y splay splay 的含义为 延伸。 S p l a y Splay Splay 主要是通过每次 将最后经过的节点延伸到根 来均摊复杂度。而延伸过程需要用到上文提到的 r o t a t e rotate rotate 函数
S p l a y Splay Splay 的定义
struct Splay {
int root, tot; // root -> 当前搜索树的根, tot -> 用来新建节点
struct Node {
int son[2]; // 左右儿子
int fa, sz; // 父亲，子树大小
int v; // 当前节点的权值
... // 一些别的参量。文艺平衡树中多有定义
}spl[N];
... // 若干函数
}Spl;
核心操作
c
o
n
n
e
c
t
{\LARGE connect}
connect
c
o
n
n
e
c
t
connect
connect 操作是用来给两个节点建立父子关系。
void connect(int p, int fa, int k) { // p 是 fa 的 k 儿子 (k = 0 代表左, k = 1 代表 右)
spl[p].fa = fa;
spl[fa].son[k] = p;
}
i
d
e
n
t
{\LARGE ident}
ident
i
d
e
n
t
ident
ident 操作是用来识别节点
p
p
p 是它父亲的左儿子还是右儿子。
int ident(int p, int fa) {
return spl[fa].son[1] == p;
}
n
e
w
n
o
d
e
{\LARGE newnode}
newnode
n
e
w
n
o
d
e
newnode
newnode 的作用是新建一个节点。
void newnode(int &p, int val, int fa) { // 建立新节点
p = ++ tot;
spl[p].fa = fa;
spl[p].val = val;
spl[p].sz = 1;
}
u
p
d
a
t
e
{\LARGE update}
update
向线段树一样，
u
p
d
a
t
e
update
update 是为了更新子树信息。代码下方的省略号表示文艺平衡树中会有更多别的信息修改。
void update(int p) {
spl[p].sz = spl[spl[p].son[0]].sz + spl[spl[p].son[1]].sz + 1;
...
}
r o t a t e {\LARGE rotate} rotate
r o t a t e rotate rotate 操作综合了 左旋( z a g zag zag) 和 右旋( z i g zig zig)。
左旋( z a g zag zag) 是指将节点 p p p 的 右儿子 旋转到 p p p 的位置。
右旋( z i g zig zig) 是指将节点 p p p 的 左儿子 旋转到 p p p 的位置。
这两种操作实际上只有一个异或 1 1 1 的改变。
而 r o t a t e rotate rotate 操作则是将任意一个节点旋转到它的父亲位置，并且不改变二叉搜索树的性质。
口诀：左旋拎右左连右，右旋拎左右连左。
解释就是：
左旋
p
p
p 就拎起右儿子，将右儿子的左儿子连在
p
p
p 的右儿子位置。将
p
p
p 连在右儿子的左儿子位置，然后将右儿子连在原来
p
p
p 在它父亲的儿子位置上。右旋同理。使用上面的
i
d
e
n
t
ident
ident 和
c
o
n
n
e
c
t
connect
connect 函数，可以比较短的写出代码：
void rotate(int p) {
int fa = spl[p].fa, ffa = spl[fa].fa, k = ident(p, fa);
connect(spl[p].son[k ^ 1], fa, k); // 从下到上的连接顺序，最好不要弄错。
connect(fa, p, k ^ 1);
connect(p, ffa, ident(fa, ffa));
update(fa); update(p);
}
s
p
l
a
y
i
n
g
{\LARGE splaying}
splaying
s
p
l
a
y
i
n
g
splaying
splaying 操作的作用是 将一个点延伸到某个位置。它也是
s
p
l
a
y
splay
splay 能够不将树高维持在
log
\log
log 复杂度却依然正确的核心。
基础的用法是 每次操作后将最后经过的点旋转到根，这样复杂度可以用 势能法 分析是均摊
log
\log
log 的（我不会）。
但是这里的延伸有一些规则，在满足规则的条件下
s
p
l
a
y
splay
splay 的复杂度才是正确的。在讲解规则前，我们先来了解 同构调整 和 异构调整 的概念：
- 同构调整
考虑点 p p p，和它的父亲 f a fa fa，以及它的爷爷 f f a ffa ffa 的位置关系，如果形态上构成一条链，那么把 p p p 延伸到 f f a ffa ffa 的位置成为同构调整。如下图两种情况
同构调整 可以先 r o t a t e ( f a ) rotate(fa) rotate(fa)，再 r o t a t e ( p ) rotate(p) rotate(p) 将 p p p 旋转到 f f a ffa ffa 的位置。
注意：虽然先 r o t a t e ( p ) rotate(p) rotate(p)，再 r o t a t e ( p ) rotate(p) rotate(p) 也可以将 p p p 旋转到 f f a ffa ffa，但是这样 会导致复杂度不正确。因此必须按照上面的顺序旋转。 - 异构调整
如果 p , f a , f f a p, fa, ffa p,fa,ffa 的位置形成 < < < 或 > > > 的形态，那么将 p p p 延伸到 f f a ffa ffa 的位置称为异构调整。
异构调整 只能先 r o t a t e ( p ) rotate(p) rotate(p)，再 r o t a t e ( p ) rotate(p) rotate(p) 将 p p p 延伸到 f f a ffa ffa 的位置。
由于旋转了两次，我们成上述两种操作为 双旋。只对 p p p 旋转称为 单旋。
那么 s p l a y i n g splaying splaying 的规则是：如果当前点 p p p 与目标位置的距离大于等于 2 2 2，那么需要判断是 同构调整 还是 异构调整 来进行相应 双旋。否则仅对 p p p 进行一次 单旋。
我们来看看具体实现：
void splaying(int p, int top) { // 将 p 旋转成 top 的儿子
if(!top) root = p; // 根的父亲是 0，所以如果top是0相当于把p旋转到根
while(spl[p].fa != top) { // 一直往上旋转
int fa = spl[p].fa, ffa = spl[fa].fa;
if(ffa != top) { // 双旋
if(ident(p, fa) == ident(fa, ffa)) rotate(fa); // 同构
else rotate(p); // 异构
}
rotate(p); // 最后都需要旋转 p，因此这样写可以简化代码
}
}
i
n
s
{\LARGE ins}
ins
i
n
s
ins
ins 操作的作用是插入一个点。根据二叉搜索树的性质找到插入点然后新建一个点即可。
void ins(int &p, int val, int fa) { // 插入一个节点 最后会splaying 不用update
if(!p) {
newnode(p, val, fa);
splaying(p, 0); // 将 p 伸展到根的位置
return ;
}
if(val <= spl[p].val) ins(spl[p].son[0], val, p); // 插左边
else ins(spl[p].son[1], val, p); // 插右边
}
d
e
l
n
o
d
e
{\LARGE delnode}
delnode
d
e
l
n
o
d
e
delnode
delnode 的作用是删掉一个节点
p
p
p。 首先需要将
p
p
p 旋转到根。如果此时
p
p
p 没有右儿子，那么令左儿子为根即可。否则就从右儿子开始一直往左递归到叶子
q
q
q。那么根据二叉搜索树的性质可得到
q
q
q 是
p
p
p 的后继。将
q
q
q 延伸到
p
p
p 的儿子位置，此时
q
q
q 一定是没有左儿子的（如果有
q
q
q 就不是
p
p
p 的后继），将
p
p
p 的左儿子连到
q
q
q 的左儿子位置，将根设置成
q
q
q 即可。
void delnode(int p) {
splaying(p, 0);
if(!spl[p].son[1]) {
root = spl[p].son[0];
spl[spl[p].son[0]].fa = 0;
}
else {
int x = spl[p].son[1];
spread(x);
while(spl[x].son[0]) {
x = spl[x].son[0];
spread(x);
}
splaying(x, p);
connect(spl[p].son[0], x, 0);
root = x; spl[x].fa = 0;
}
}
其余查找操作都可以根据二叉搜索树的性质查找。但是 一定要将最后经过的点旋转到根。
例题：
普通平衡树(数据加强版)
CODE：
// Splay 模板
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
struct Splay {
int root, tot; // 根 节点数
struct Node { // 节点
int son[2]; // 左右儿子
int fa, sz, val; // 父亲, 子树大小， 这个节点的权值
}spl[N];
void connect(int x, int fa, int k) { // x 是 fa 的 k 儿子
spl[fa].son[k] = x;
spl[x].fa = fa;
}
int ident(int x, int fa) { // 检验 x 是 fa 的 左/右儿子
return spl[fa].son[1] == x;
}
void update(int p) {
spl[p].sz = spl[spl[p].son[0]].sz + spl[spl[p].son[1]].sz + 1;
}
void rotate(int p) { // 将 p 旋转到它父亲的位置
int fa = spl[p].fa, ffa = spl[fa].fa, k = ident(p, fa);
connect(spl[p].son[k ^ 1], fa, k);
connect(fa, p, k ^ 1);
connect(p, ffa, ident(fa, ffa));
update(fa); update(p);
}
void splaying(int p, int top) { // 将 p 旋转成 top 的儿子
if(!top) root = p;
while(spl[p].fa != top) { // 一直往上旋转
int fa = spl[p].fa, ffa = spl[fa].fa;
if(ffa != top) { // 双旋
if(ident(p, fa) == ident(fa, ffa)) rotate(fa);
else rotate(p);
}
rotate(p);
}
}
void newnode(int &p, int val, int fa) { // 建立新节点
p = ++ tot;
spl[p].fa = fa;
spl[p].val = val;
spl[p].sz = 1;
}
void ins(int &p, int val, int fa) { // 插入一个节点 最后会splaying 不用update
if(!p) {
newnode(p, val, fa);
splaying(p, 0); // 将 p 伸展到根的位置
return ;
}
if(val <= spl[p].val) ins(spl[p].son[0], val, p); // 插左边
else ins(spl[p].son[1], val, p); // 插右边
}
void delnode(int p) { // 删掉 p 节点 首先将节点旋转到根，然后找后继
splaying(p, 0);
if(!spl[p].son[1]) { // 没有后继
root = spl[p].son[0];
spl[root].fa = 0;
return ;
}
else { // 存在后继
int x = spl[p].son[1];
while(spl[x].son[0]) x = spl[x].son[0]; // 找左儿子
splaying(x, p); // 这时候 x 一定是没有左儿子的
root = x; spl[x].fa = 0; // 变成根
connect(spl[p].son[0], x, 0);
update(x);
}
}
void del(int p, int val) { // 删除权值val 首先先找到这个节点，然后把它旋转到根，然后再删掉
if(spl[p].val == val) {
delnode(p);
return ;
}
if(val < spl[p].val) del(spl[p].son[0], val);
else del(spl[p].son[1], val);
}
int rank(int val) { // 查 val 的排名
int p = root, pre = 0, rk = 1; // pre 表示上一次经过的节点
while(p) {
pre = p;
if(val <= spl[p].val) p = spl[p].son[0];
else rk += spl[spl[p].son[0]].sz + 1, p = spl[p].son[1];
}
if(pre) splaying(pre, 0);
return rk;
}
int Kth(int k) { // 查询第k小
int p = root, pre = 0, res = 0;
while(p) {
pre = p;
if(spl[spl[p].son[0]].sz + 1 == k) {pre = p; res = spl[p].val; break;}
else if(spl[spl[p].son[0]].sz >= k) p = spl[p].son[0];
else k -= (spl[spl[p].son[0]].sz + 1), p = spl[p].son[1];
}
if(pre) splaying(pre, 0);
return res;
}
}Spl;
int n, m, lstans, res;
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++ ) {
int x; scanf("%d", &x);
Spl.ins(Spl.root, x, 0);
}
for(int i = 1; i <= m; i ++ ) {
int opt, x; scanf("%d%d", &opt, &x);
x ^= lstans;
if(opt == 1) Spl.ins(Spl.root, x, 0);
if(opt == 2) Spl.del(Spl.root, x);
if(opt == 3) lstans = Spl.rank(x), res ^= lstans;
if(opt == 4) lstans = Spl.Kth(x), res ^= lstans;
if(opt == 5) lstans = (Spl.Kth(Spl.rank(x) - 1)), res ^= lstans; // 前驱
if(opt == 6) lstans = (Spl.Kth(Spl.rank(x + 1))), res ^= lstans; // 后继
}
cout << res << endl;
return 0;
}
文艺平衡树（序列操作）
普通平衡树是用来维护集合的。
所谓文艺平衡树，就是使用 平衡树维护序列。
我们序列每个数以 下标 为关键值建立平衡树。那么这个平衡树的中序遍历就是原序列。
一棵子树可以代表一段区间，每个节点可以维护一些额外信息表示它的子树对应区间的信息。
文艺平衡树可以支持很多序列操作，它可以支持一般的线段树操作，并且还能够支持 区间翻转，在序列某个位置插入元素 等线段树不能完成的操作。
下面我们来通过一道例题学习一下：
【模板】文艺平衡树
题意：
给你一个长度为
n
n
n 的有序序列
a
i
a_i
ai，有
m
m
m 次操作，每次操作给出
l
,
r
l, r
l,r 表示把
[
l
,
r
]
[l, r]
[l,r] 区间翻转。求
m
m
m 次操作后的序列。
数据规模：
1
≤
n
,
m
≤
100000
1 \leq n, m \leq 100000
1≤n,m≤100000。
分析：
首先按照下标为关键值建立平衡树，同时记录每个节点存储的真实值。
对于一次操作 ( l , r ) (l, r) (l,r)，找到 l − 1 l - 1 l−1 所在的节点 p p p 并将它延伸到根，然后找到 r + 1 r + 1 r+1 对应的节点 q q q 并将它延伸到 p p p 的儿子位置。由于当 l = 1 l = 1 l=1 或 r = n r = n r=n 时会找到空节点，因此我们开始时就插入 0 0 0 和 n + 1 n + 1 n+1 这两个 哨兵节点 来处理边界。
由于延伸操作不改变二叉树的中序遍历，那么此时 q q q 的左儿子对应的子树就是 [ l , r ] [l, r] [l,r] 区间。记这个左儿子为 s o n q , 0 son_{q, 0} sonq,0
对于区间翻转操作，相当于就是 交换
s
o
n
q
,
0
son_{q, 0}
sonq,0 子树中的所有节点的左右儿子。因为这样就可以将遍历顺序倒过来。
所以我们类比 线段树区间修改 操作，将
s
o
n
q
,
0
son_{q, 0}
sonq,0 的左右儿子交换，并打上标记。标记的含义表示当前节点的信息已经修改过了，但是还没有往下传，如果经过一个节点就把标记下传。
需要注意的是我们 不能让向上延伸的点所要经过的路径上存在没有下传的标记，否则会因为父子关系的改变导致标记传给本来不应该传递的点。因此每次 s p l a y i n g splaying splaying 一个点之前，都应该先使用 F i n d Find Find 函数从上至下找到它，在找的过程中顺便把经过的所有点的标记下传。
最后找到每个位置上的点并输出它的真实值即可。
时间复杂度
O
(
m
×
log
2
n
)
O(m \times \log_2n)
O(m×log2n)
F i n d Find Find 函数：
int Find(int x) { // 找到 排名为 x 的节点
int p = root;
while(p) {
spread(p);
if(spl[spl[p].son[0]].sz + 1 == x) return p;
else if(spl[spl[p].son[0]].sz >= x) p = spl[p].son[0];
else x -= spl[spl[p].son[0]].sz + 1, p = spl[p].son[1];
}
}
CODE：
// 文艺平衡树
// 支持序列翻转, 这个是平衡树做不到的
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, a[N];
struct Splay {
int root, tot;
struct Node {
int son[2], fa;
int sz, val, rev;
}spl[N];
void update(int p) {
spl[p].sz = spl[spl[p].son[0]].sz + spl[spl[p].son[1]].sz + 1;
}
void connect(int p, int fa, int k) { // 建立父子关系
spl[p].fa = fa;
spl[fa].son[k] = p;
}
int ident(int p, int fa) {
return spl[fa].son[1] == p;
}
void rotate(int p) {
int fa = spl[p].fa, ffa = spl[fa].fa, k = ident(p, fa);
connect(spl[p].son[k ^ 1], fa, k);
connect(fa, p, k ^ 1);
connect(p, ffa, ident(fa, ffa));
update(fa); update(p);
}
void splaying(int p, int top) {
if(!top) root = p;
while(spl[p].fa != top) {
int fa = spl[p].fa, ffa = spl[fa].fa;
if(ffa != top) { // 双旋
if(ident(fa, ffa) == ident(p, fa)) rotate(fa);
else rotate(p);
}
rotate(p);
}
}
void spread(int p) { // 传递翻转标记
if(spl[p].rev) {
swap(spl[p].son[0], spl[p].son[1]);
spl[spl[p].son[0]].rev ^= 1;
spl[spl[p].son[1]].rev ^= 1;
spl[p].rev = 0;
}
}
int Find(int x) { // 找到 排名为 x 的节点
int p = root;
while(p) {
spread(p);
if(spl[spl[p].son[0]].sz + 1 == x) return p;
else if(spl[spl[p].son[0]].sz >= x) p = spl[p].son[0];
else x -= spl[spl[p].son[0]].sz + 1, p = spl[p].son[1];
}
}
int build(int l, int r) {
if(l > r) return 0;
int p = ++ tot;
if(l == 0 && r == n + 1) spl[p].fa = 0;
if(l == r) {
spl[tot].sz = 1;
spl[tot].val = a[l];
return p;
}
int mid = (l + r >> 1);
spl[p].val = a[mid];
spl[p].son[0] = build(l, mid - 1);
if(spl[p].son[0]) connect(spl[p].son[0], p, 0);
spl[p].son[1] = build(mid + 1, r);
if(spl[p].son[1]) connect(spl[p].son[1], p, 1);
update(p);
return p;
}
void Rev(int l, int r) { // 翻转 [l, r] 区间
int p = root;
l = Find(l), r = Find(r + 2); // 找到l - 1, r + 1 所在编号，其实是为了传懒标记
splaying(l, 0); splaying(r, l);
spl[spl[r].son[0]].rev ^= 1;
}
int rank(int k) {
int p = root, pre = 0, res = 0;
while(p) {
spread(p); pre = p;
if(spl[spl[p].son[0]].sz + 1 == k) {res = spl[p].val; break;}
else if(spl[spl[p].son[0]].sz >= k) p = spl[p].son[0];
else k -= spl[spl[p].son[0]].sz + 1, p = spl[p].son[1];
}
if(pre) splaying(pre, 0);
return res;
}
}Spl;
int main() {
scanf("%d%d", &n, &m);
for(int i = 0; i <= n + 1; i ++ ) a[i] = i;
Spl.root = Spl.build(0, n + 1);
for(int i = 1; i <= m; i ++ ) {
int l, r; scanf("%d%d", &l, &r);
Spl.Rev(l, r);
}
for(int i = 2; i <= n + 1; i ++ ) {
printf("%d ", Spl.rank(i));
}
return 0;
}
文艺平衡树的功能非常强大，可以用它来完成一些线段树操作。比如区间加，求最大子段和等。
操作的关键在于
s
p
r
e
a
d
spread
spread 函数（向下传递懒标记）和
u
p
d
a
t
e
update
update 函数。(向上修改子树信息)
u
p
d
a
t
e
update
update 函数一般会在 树的形态发生改变 时用到。所以
r
o
t
a
t
e
rotate
rotate 函数和
d
e
l
n
o
d
e
delnode
delnode 函数一般有
u
p
d
a
t
e
update
update。另外区间修改后也需要向上
u
p
d
a
t
e
update
update 两次。
对于一次区间修改（单点改也可以看作区间修改），我们一般的写法是：
- 使用 F i n d Find Find 函数找到两个节点 p , q p, q p,q，同时将沿路所有标记下传
- s p l a y i n g ( p , 0 ) splaying(p, 0) splaying(p,0)， s p l a y i n g ( q , p ) splaying(q, p) splaying(q,p)
- 修改 s o n q , 0 son_{q, 0} sonq,0 的信息。
- u p d a t e ( q ) update(q) update(q)， u p d a t e ( p ) update(p) update(p)
对于区间查询或者删除某个点，都需要先使用 F i n d Find Find 函数传递标记。
练习题
平衡树维护序列
P2596 [ZJOI2006] 书架
需要支持在序列上单点插入，单点删除，查询某个位置上的值，查询某个值所在的位置。
以下标为关键字建立
S
p
l
a
y
Splay
Splay，同时维护 每个值所在的节点编号。前三种操作正常，第四种操作在这个节点往上跳的过程中计算。
P4036 [JSOI2008] 火星人
对每个询问二分答案。转化成你需要支持在序列上插入字符，修改字符，查询区间
h
a
s
h
hash
hash 值。
用
S
p
l
a
y
Splay
Splay 维护 文艺平衡树，平衡树的每个节点维护它的子树对应区间的
h
a
s
h
hash
hash 值。
P2042 [NOI2005] 维护数列
史题。所有操作平衡树都可以直接维护。但是有两个点需要注意：
- 删掉的节点编号可以放到一个数组里，下次新建直接使用减少空间复杂度。
- 对于往一个位置后插入若干数的操作，可以先把这些数建成一棵小的平衡树再插入，不要每次插入一个，复杂度会变劣。
P3215 [JSOI2011] 括号序列
挺好的题。
相当于给你一个
0
/
1
0/1
0/1 序列，你需要支持 区间赋值，区间翻转，区间异或
1
1
1，区间查询最少将多少
0
/
1
0/1
0/1 反转使区间满足括号匹配的性质。
建立一棵文艺平衡树。前三种操作的维护是简单的。
对于查询，一个很对的策略是将所有数依次入栈，能匹配就直接弹栈。最后肯定剩下形如
1111...000..
1111...000..
1111...000..。设
x
x
x 表示
1
1
1 的数量，
y
y
y 表示
0
0
0 的数量。那么答案就是
⌊
x
2
⌋
+
⌊
y
2
⌋
+
(
x
m
o
d
2
)
+
(
y
m
o
d
2
)
\left \lfloor \frac{x}{2} \right \rfloor + \left \lfloor \frac{y}{2} \right \rfloor + (x\mod 2) + (y \mod 2)
⌊2x⌋+⌊2y⌋+(xmod2)+(ymod2) 。
平衡树维护这些信息即可。
平衡树维护数集
CF702F T-Shirts
感觉是很厉害的题。
考虑按照
q
i
q_i
qi 从大到小扫每个物品，设物品的价值为
c
i
c_i
ci。那么每次相当于把所有
v
i
v_i
vi 大于等于
c
i
c_i
ci 的人的
v
i
v_i
vi 减去
c
i
c_i
ci，答案加
1
1
1。
将所有
v
i
v_i
vi 放进平衡树中维护。但是不可能每次将所有
v
i
v_i
vi 大于等于
c
i
c_i
ci 的数删掉再插进去。
考虑将所有数分成
[
0
,
c
i
)
[0, c_i)
[0,ci)，
[
c
i
,
2
c
i
)
[c_i, 2c_i)
[ci,2ci)，
[
2
c
i
,
I
N
F
)
[2c_i, INF)
[2ci,INF) 三组。
对于第一组，没有影响。
对于第二组，暴力将节点删除，将值更新后插入。
对于第三组，它们再平衡树上的位置不会变化，整体打上一个减法标记。
对于第二组，这些数每次至少减少一半。因此一个数最多被取出 log V \log V logV 次。因此总复杂度是 O ( n log V log n ) O(n \log V \log n) O(nlogVlogn) 的。
这个题还可以用 平衡树的有交合并 做。但是这个算法只能用 F H Q − t r e a p FHQ-treap FHQ−treap 维护，具体思路看下面。
F H Q t r e a p FHQ \ treap FHQ treap（无旋 t r e a p treap treap）
简介
F
H
Q
−
t
r
e
a
p
FHQ-treap
FHQ−treap 是一种特殊的
t
r
e
a
p
treap
treap。
其维护树高的方式和
t
r
e
a
p
treap
treap 一样，都是根据随机值维护堆的形态。
但与
t
r
e
a
p
treap
treap 的旋转调整结构不同，
F
H
Q
−
t
r
e
a
p
FHQ-treap
FHQ−treap 不需要旋转。其核心操作为 分裂 与 合并。
它的操作形式使它很容易支持维护序列，可持久化。
核心操作
定义
int root, tot;
int rt1, rt2, rt3;
struct Node {
int son[2];
int sz, v;
LL w; // v 为权值， w 为随机值
... // 一些别的子树信息
}t[N];
其中 r t 1 , r t 2 , r t 3 rt_1,rt_2, rt_3 rt1,rt2,rt3 是用来承接分裂时得到的子树根。
分裂
称用来排序的比较值为 关键值。下面以数值作为关键值为例，即 平衡树维护数集 模型。
s p l i t ( p , l i m , & x , & y ) split(p, lim, \& x, \& y) split(p,lim,&x,&y) 的作用是将以 p p p 为根的子树按照关键值 l i m lim lim 分裂成两棵子树，满足一棵子树中关键值小于等于 l i m lim lim，另一棵关键值都大于 l i m lim lim，并且得到两棵子树根的编号。
称分裂得到的两棵子树中，所有点的关键值都小于等于
l
i
m
lim
lim 的子树为 左树，都大于
v
v
v 的为 右树。
根据平衡树二叉搜索树 左小右大 的特性，可以得到以下分裂过程：
-
比较根节点的关键值 与 给定关键值的大小关系：
1.若根节点的关键值 小于等于 给定关键值，那么将根与左子树都划分到左树中。向右子树递归，继续分裂子树。
2.若根节点的关键值 大于 给定关键值，那么将根与右子树都划分到右树中。向左子树递归，继续分裂子树。 -
递归到叶子，结束。
由于树高为
log
2
n
\log_2 n
log2n，因此单次分裂的时间复杂度为
O
(
log
2
n
)
O(\log_2 n)
O(log2n)。
代码：
void split(int p, LL lim, int &x, int &y) {
if(!p) {x = y = 0; return ;}
if(t[p].v <= lim) x = p, split(t[p].son[1], lim, t[p].son[1], y);
else y = p, split(t[p].son[0], lim, x, t[p].son[0]);
update(p);
}
合并
M
e
r
g
e
(
x
,
y
)
Merge(x, y)
Merge(x,y) 的作用是将
x
,
y
x,y
x,y 的子树合并为一棵，并且返回合并后树根的编号。
需要特别注意：合并的两棵树必须满足
x
x
x 中点的权值都小于等于
y
y
y 中的权值，即没有交叉。如果存在交叉，则需要平衡树的有交并。这个科技下面会讲到。
由于
x
x
x 子树中任一点权值都小于等于
y
y
y 中任一点权值，因此只需要比较随机值来维护堆的形态即可。
设
x
x
x 对应的子树为左树，
y
y
y 对应的子树为右树。
过程：
- 若左树根的随机值小于右树根，就将左树根定为当前根，将右树与左树的右子树接着合并。
- 若右树根的随机值小于左树根，就将右树根定为当前根，将左树与右树的左子树接着合并。
- 如果有有一棵树为空，就返回另一棵树的根。
由于树高为
log
2
n
\log_2 n
log2n，因此单次合并的复杂度为
O
(
log
2
n
)
O(\log_2 n)
O(log2n)。
代码：
int Merge(int p, int q) {
if(!p || !q) return p ^ q;
if(t[p].w < t[q].w) {
t[p].son[1] = Merge(t[p].son[1], q);
update(p);
return p;
}
else {
t[q].son[0] = Merge(p, t[q].son[0]);
update(q);
return q;
}
}
基本操作
u
p
d
a
t
e
{\LARGE update}
update
u
p
d
a
t
e
(
p
)
update(p)
update(p) 用来向上更新子树信息。
void update(int p) {
t[p].sz = t[t[p].son[0]].sz + t[t[p].son[1]].sz + 1;
... // 一些别的传递信息
}
n
e
w
n
o
d
e
{\LARGE newnode}
newnode
n
e
w
n
o
d
e
(
v
)
newnode(v)
newnode(v) 是用来新建一个权值为
w
w
w 的节点，并返回节点编号。
int newnode(int w) {
tot ++;
t[tot] = (Node) {{0, 0}, 1, v, rnd()};
return tot;
}
i
n
s
{\LARGE ins}
ins
i
n
s
(
v
)
ins(v)
ins(v) 是用来插入一个值为
v
v
v 的数。
先按照
v
v
v 将原来树分裂，然后将
v
v
v 合并到左树，再将左右树合并。
复杂度
O
(
log
2
n
)
O(\log_2 n)
O(log2n)
void ins(int v) {
split(root, v, rt1, rt2);
root = Merge(Merge(rt1, newnode(v)), rt2);
}
d
e
l
{\LARGE del}
del
d
e
l
(
v
)
del(v)
del(v) 的作用是删掉一个值为
v
v
v 的数。
先按照
v
v
v 将原来的树分成左右子树，然后将左树按照
v
−
1
v-1
v−1 分裂成两颗子树。将此时新生成的右树的根节点删掉，然后将三棵树合并即可。
复杂度
O
(
log
2
n
)
O(\log_2 n)
O(log2n)
void del(int v) {
split(root, v, rt1, rt2);
split(rt1, v - 1, rt1, rt3);
rt3 = Merge(t[rt3].son[0], t[rt3].son[1]);
root = Merge(Merge(rt1, rt3), rt2);
}
r
a
n
k
{\LARGE rank}
rank
r
a
n
k
(
v
)
rank(v)
rank(v) 的作用是查询
v
v
v 在数集中的排名。
按照
v
−
1
v-1
v−1 分裂，
v
v
v 的排名就是左树大小
+
1
+1
+1。
复杂度
O
(
log
2
n
)
O(\log_2 n)
O(log2n)
int rank(int v) {
split(root, v - 1, rt1, rt2);
int ans = t[rt1].sz + 1;
root = Merge(rt1, rt2);
return ans;
}
K
t
h
{\LARGE Kth}
Kth
K
t
h
(
x
)
Kth(x)
Kth(x) 的作用是找到序列中排名为
x
x
x 的数。
根据平衡树二叉搜索树的性质，直接从上到下找比较子树大小和剩余数量即可。
复杂度
O
(
log
2
n
)
O(\log_2 n)
O(log2n)
int Kth(int p, int x) { // 查询第 x 个
while(p) {
if(t[t[p].son[0]].sz >= x) p = t[p].son[0];
else if(t[t[p].son[0]].sz + 1 == x) return t[p].v;
else x -= t[t[p].son[0]].sz + 1, p = t[p].son[1];
}
}
一些别的操作可以由上述操作组合完成。
关键都是在于使用
s
p
l
i
t
split
split 和
M
e
r
g
e
Merge
Merge 函数。
文艺平衡树（序列操作）
同维护数集的方式一样，只需要将关键值变为下标即可。
能够支持线段树的所有操作：区间加，区间求和，求最大子段和… 并且也能支持 单点插入，区间翻转 等。
对于一个区间修改或区间查询，假设区间为
[
l
,
r
]
[l, r]
[l,r]。
那么做法是先按照
r
r
r 分裂成
[
1
,
r
]
[1, r]
[1,r] 和
[
r
+
1
,
n
]
[r + 1, n]
[r+1,n]，然后按照
l
−
1
l - 1
l−1 将
[
1
,
r
]
[1, r]
[1,r] 分裂成
[
1
,
l
−
1
]
[1, l - 1]
[1,l−1] 和
[
l
,
r
]
[l, r]
[l,r]。查询或打标记
[
l
,
r
]
[l, r]
[l,r] 对应子树即可。
需要注意的是：
在 分裂 与 合并 时需要向下传递标记，回溯的时候也需要向上传递信息。
单点查询与修改只需要根据二叉搜索树的性质找到对应节点即可。
文艺平衡树不需要插入哨兵节点。
平衡树的有交并
一个很
N
B
NB
NB 的科技。
首先先来思考一个问题：对于
F
H
Q
−
t
r
e
a
p
FHQ-treap
FHQ−treap 的合并操作，我们必须要求左树和右树不交（文艺平衡树肯定不交），这是为什么呢？
因为这样每次确定当前根，根的左右子树至少有一个已经定下来了，我们只需要接着去确定根的另一棵子树。由于树高为
log
2
n
\log_2n
log2n，因此我们只会确定
log
2
n
\log_2 n
log2n 次根，复杂度为
O
(
log
2
n
)
O(\log_2n)
O(log2n)。
那如果左右树有交呢？发现我们未必能确定根的一棵子树的形态，还需要分别往左右子树确定。
但是平衡树的有交并告诉我们：直接暴力的往左右子树合并，复杂度就是均摊
O
(
log
V
log
n
)
O(\log V \log n)
O(logVlogn)。
怎么做呢？其实很简单：
设当前合并的子树为
p
,
q
p, q
p,q。注意
p
,
q
p, q
p,q 中的权值可能有交。
p
,
q
p, q
p,q 的权值分别为
v
p
,
v
q
v_p, v_q
vp,vq。
- 比较
p
,
q
p, q
p,q 的随机值大小。
1.若 p p p 的随机值更大，那么将 p p p 作为当前根。然后将 q q q 的子树按照 v p v_p vp 分裂为左右树 l q , r q l_q, r_q lq,rq。将 l q l_q lq 与 l s p ls_p lsp 合并作为根的左子树， r q r_q rq 和 r s p rs_p rsp 合并作为根的右子树。
2.若 q q q 的随机值更大，那么将 q q q 作为当前根。然后将 p p p 的子树按照 v q v_q vq 分裂为左右树 l p , r p l_p, r_p lp,rp。将 l p l_p lp 与 l s q ls_q lsq 合并作为根的左子树， r p r_p rp 和 r s q rs_q rsq 合并作为根的右子树。 - 如果 p , q p, q p,q 有一个为空，则返回另一个。
注意：
注意到对于当前要分裂的树而言，设另一棵树根的值为
v
v
v，那么实际上按照
v
v
v 还是
v
−
1
v - 1
v−1 分裂都能满足二叉搜索树的性质。但是我们每次都把
v
v
v 分到左树中，这样有可能会导致树高增大很多（我也不懂为啥）。因此每次分裂我们随机一个值
w
∈
{
0
,
1
}
w \in \{0, 1\}
w∈{0,1}，然后按照
v
−
w
v - w
v−w 分裂。这样就不会
T
T
T 了。
代码：
int Merge(int p, int q) { // 有交合并
if(!p || !q) return p ^ q;
spread(p); spread(q);
if(t[p].w < t[q].w) {
int r1, r2;
int w = rnd() % 2;
split(q, t[p].v - w, r1, r2); // 分裂
t[p].son[0] = Merge(t[p].son[0], r1);
t[p].son[1] = Merge(t[p].son[1], r2);
return p;
}
else {
int r1, r2;
int w = rnd() % 2;
split(p, t[q].v - w, r1, r2);
t[q].son[0] = Merge(r1, t[q].son[0]);
t[q].son[1] = Merge(r2, t[q].son[1]);
return q;
}
练习题
P10284 [USACO24OPEN] Splitting Haybales P
分析：
考虑对
r
r
r 扫描线，同时维护所有
l
l
l 的答案。
扫到一个
l
l
l，我们将
B
B
B 的草量将去
E
E
E 的草量插入数集中。
那么每扫到一个
r
r
r，要做的就是将数集里小于等于
0
0
0 的数
+
a
r
+a_{r}
+ar，将大于
0
0
0 的数
−
a
r
-a_r
−ar。
平衡树的分裂可以做到将数集分成两部分，修改只需要打标记，最后有交并维护平衡树的形态即可。
复杂度
O
(
n
log
2
V
log
2
n
)
O(n \log_2V \log_2n)
O(nlog2Vlog2n)
CODE：
// fhq_treap
// 平衡树的有交合并
// 支持单点插入， 有交合并
#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
mt19937_64 rnd(time(0));
int idq[N];
LL ans[N];
struct fhq_treap {
int root, tot;
int rt1, rt2, rt3;
struct Node {
int son[2];
int fa;
LL v, w, tag; // tag 表示加减标记
}t[N];
void init(int p, LL c) {
t[p].v += c;
t[p].tag += c;
}
void spread(int p) {
if(t[p].tag) {
if(t[p].son[0]) init(t[p].son[0], t[p].tag);
if(t[p].son[1]) init(t[p].son[1], t[p].tag);
t[p].tag = 0;
}
}
void split(int p, LL lim, int &x, int &y) {
if(!p) {x = y = 0; return ;}
spread(p);
if(t[p].v <= lim) x = p, split(t[p].son[1], lim, t[p].son[1], y);
else y = p, split(t[p].son[0], lim, x, t[p].son[0]);
if(t[p].son[0]) t[t[p].son[0]].fa = p;
if(t[p].son[1]) t[t[p].son[1]].fa = p;
}
int Merge(int p, int q) { // 有交合并
if(!p || !q) return p ^ q;
spread(p); spread(q);
if(t[p].w < t[q].w) {
int r1, r2;
int w = rnd() % 2;
split(q, t[p].v - w, r1, r2); // 分裂
t[p].son[0] = Merge(t[p].son[0], r1);
t[p].son[1] = Merge(t[p].son[1], r2);
if(t[p].son[0]) t[t[p].son[0]].fa = p;
if(t[p].son[1]) t[t[p].son[1]].fa = p;
t[p].fa = 0;
return p;
}
else {
int r1, r2;
int w = rnd() % 2;
split(p, t[q].v - w, r1, r2);
t[q].son[0] = Merge(r1, t[q].son[0]);
t[q].son[1] = Merge(r2, t[q].son[1]);
if(t[q].son[0]) t[t[q].son[0]].fa = q;
if(t[q].son[1]) t[t[q].son[1]].fa = q;
t[q].fa = 0;
return q;
}
}
int newnode(LL v, int id) {
tot ++;
t[tot] = (Node) {{0, 0}, 0, v, rnd(), 0};
idq[id] = tot;
return tot;
}
void ins(LL v, int o) { // 插入一个权值 v
split(root, v, rt1, rt2);
root = Merge(Merge(rt1, newnode(v, o)), rt2);
}
void change(LL v) { // 一个操作 v
split(root, 0, rt1, rt2);
if(rt1) init(rt1, v);
if(rt2) init(rt2, -v);
root = Merge(rt1, rt2);
}
void dfs(int x) {
if(!x) return ;
dfs(t[x].fa);
spread(x);
}
LL query(int id) {
dfs(idq[id]);
return t[idq[id]].v;
}
void print() {
for(int i = 1; i <= tot; i ++ ) {
printf("t[%d].v = %lld t[%d].ls = %d t[%d].rs = %d t[%d].fa = %d\n", i, t[i].v, i, t[i].son[0], i, t[i].son[1], i, t[i].fa);
}
}
} trp;
int n, q;
LL a[N], sv[N];
vector< int > add[N], del[N];
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i ++ ) {
scanf("%lld", &a[i]);
}
scanf("%d", &q);
for(int i = 1; i <= q; i ++ ) {
int l, r;
scanf("%d%d%lld", &l, &r, &sv[i]);
add[l].pb(i); del[r].pb(i);
}
for(int i = 1; i <= n; i ++ ) {
for(auto v : add[i]) {
trp.ins(sv[v], v);
}
trp.change(a[i]);
for(auto v : del[i]) ans[v] = trp.query(v);
}
for(int i = 1; i <= q; i ++ ) printf("%lld\n", ans[i]);
return 0;
}
P2611 [ZJOI2012] 小蓝的好友
分析：
首先答案等于矩形的总数量减去不存在一个关键点的矩形数。
然后按照行从上往下扫，维护每一列向上延伸没有关键点的高度
h
i
h_i
hi。
计算以当前行为底不包含一个关键点的矩形数量是简单的：根据
h
i
h_i
hi 建出笛卡尔树，然后树形
d
p
dp
dp 即可。
由于关键点分布随机，因此
h
i
h_i
hi 的大小也是随机的。因此这棵笛卡尔树可以看作是一棵树高为
log
2
n
\log_2n
log2n 的文艺平衡树。
那么相当于需要支持单点删除，单点插入。计算答案在
u
p
d
a
t
e
update
update 函数中算即可。
CODE：
// fhq_treap
// 需要支持单点删除
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long LL;
mt19937_64 rnd(time(0));
int R, C, n;
LL res;
struct fhq_treap {
int root, tot;
int rt1, rt2, rt3;
struct Node {
int son[2];
int sz, w;
LL tag, ans;
}t[N];
void update(int p) {
t[p].sz = t[t[p].son[0]].sz + t[t[p].son[1]].sz + 1;
t[p].ans = t[t[p].son[0]].ans + t[t[p].son[1]].ans + 1LL * t[p].w * (t[t[p].son[0]].sz + 1LL) * (t[t[p].son[1]].sz + 1);
}
void add(int p, int c) {
t[p].tag += c;
t[p].w += c;
t[p].ans += 1LL * c * t[p].sz * (t[p].sz + 1) / 2LL;
}
void split(int p, int k, int &x, int &y) {
if(!p) {x = y = 0; return ;}
if(t[t[p].son[0]].sz + 1 <= k) x = p, split(t[p].son[1], k - (t[t[p].son[0]].sz + 1), t[p].son[1], y);
else y = p, split(t[p].son[0], k, x, t[p].son[0]);
update(p);
}
int Merge(int p, int q) {
if(!p || !q) return p ^ q;
if(t[p].w < t[q].w) {
t[p].son[1] = Merge(t[p].son[1], q);
update(p);
return p;
}
else {
t[q].son[0] = Merge(p, t[q].son[0]);
update(q);
return q;
}
}
int newnode(int w) {
tot ++;
t[tot] = (Node) {{0, 0}, 1, w, 0, 0};
return tot;
}
void del(int x) { // 删掉一个下标
split(root, x, rt1, rt2);
split(rt1, x - 1, rt1, rt3);
root = Merge(rt1, rt2);
}
void ins(int x, int w) { // 插入一个值 前面有 x - 1 个
split(root, x, rt1, rt2);
root = Merge(Merge(rt1, newnode(w)), rt2);
}
void Add() {
add(root, 1);
}
} trp;
struct node {
int x, y;
}d[N];
bool cmp(node a, node b) {
return ((a.x < b.x) || (a.x == b.x && a.y < b.y));
}
inline LL f(int x) {
return 1LL * x * (x + 1);
}
int main() {
scanf("%d%d%d", &R, &C, &n);
for(int i = 1; i <= n; i ++ )
scanf("%d%d", &d[i].x, &d[i].y);
sort(d + 1, d + n + 1, cmp);
int p = 1;
for(int i = 1; i <= C; i ++ ) trp.ins(i - 1, 0);
for(int i = 1; i <= R; i ++ ) {
trp.Add();
while(p <= n && d[p].x == i) {
trp.del(d[p].y);
trp.ins(d[p].y - 1, 0);
p ++;
}
res += trp.t[trp.root].ans;
}
LL ans = 0;
ans = f(R) / 2LL * f(C) / 2LL;
printf("%lld\n", ans - res);
return 0;
}