平衡树是一种比线段树更加强大的数据结构，它能维护很多线段树无法维护的操作和信息，比如插入、删除、反转。

~~我是 splay 批~~

splay

维护的基本信息

$root\And tot$，根节点和节点个数。
$ch_{u,0/1}$，左右儿子。
$val_u$，该节点维护的数值。
$fa_u$，父亲节点。
$cnt_u$，该节点重复的次数。（$val$ 一样就重叠在一起）
$siz_u$，表示该节点子树内有多少个点（计算重点数量）

$\verb|push_up|$，$\verb|clear|$ 和 $\verb|get|$

$\verb|push_up|$：更新该节点维护的信息。

$\verb|clear|$：销毁节点，清除上面所有的信息。

$\verb|get|$：判定节点 $u$ 是父亲的左/右儿子。

1	int get(int x) {return x==ch[fa[x]][1];}

$\verb|rotate|$

splay 的平衡性是由 $\verb|splay|$ 操作保证的，而 $\verb|splay|$ 操作是基于旋转操作实现的。

旋转操作就是将一个节点 $u$ 移动到其父亲的位置，同时不改变 BST 的性质。

如图就是一个旋转的例子，两边的树中序遍历均为 bxcya。

不妨考虑右旋的情况，从这个图中就可以看出旋转的方式：

为了交换 $x$ 与 $y$ 的位置，我们需要将 $x$ 挪到 $y$ 父亲的位置，为此需要将 $y$ 的父亲设为 $x$，并且将 $x$ 的右儿子设为 $y$。
然而为了维持中序遍历，我们需要将 $c$ 从 $x$ 的右儿子改为 $y$ 的左儿子。这一步需要在上面那一步之前就完成。
最后如果原来 $y$ 还有父亲 $z$ 那么就需要修改 $x$ 的父亲和 $z$ 的儿子。

实现成代码也很简单：

void rotate(int x) {
	int y=fa[x],z=fa[y],chk=get(x);
  		//chk确定x的方向，
		//将两种旋转统一为一种
	ch[y][chk]=ch[x][chk^1];
	if(ch[x][chk^1]) fa[ch[x][chk^1]]=y;
	ch[x][chk^1]=y;
	fa[y]=x,fa[x]=z;
	if(z) ch[z][y==ch[z][1]]=x;
	push_up(y),push_up(x);
}

$\verb|splay|$

splay 树的核心操作，作用是利用 $\verb|splay|$ 操作将节点 $x$ 翻到根节点的位置。

定义 $f$ 为 $x$ 的父亲节点。主要的旋转方式有三种：

zig

只在 $f$ 为根节点时进行，只需要将 $x$ $\verb|rotate|$ 上去即可。

zig-zig

在 $\verb|get|(x)=\verb|get|(f)$ 时进行，操作是先旋转 $f$ 再旋转 $x$。

zig-zag

其实可以发现对一个链的底部做 $\verb|splay|$，链的长度会除以 $2$。

splay 树的复杂度保证在每当访问一个节点后都要将其 $\verb|splay|$ 到根节点位置。

当然还有旋转到某祖先的儿子的操作。

可以证明，进行一次 $\verb|splay|$ 操作的均摊时间复杂度是 $O(\log n)$。

il void splay(int x,int tar) {
	if(!tar) root=x;
	for(int f=fa[x];(f=fa[x])!=tar;rotate(x)) {
		if(fa[f]!=tar) rotate(get(x)==get(f)?f:x);
	}
}

$\verb|insert|\And\verb|delete|$

$\verb|insert|$ 的思路就是找到对应的位置，并建立新的节点。

$\verb|delete|$ 的思路更加暴力，我们先找到对应的节点并且旋转到根节点，然后判断子树是否为空，如果有一个是空的就将另一个的根设为整个子树的根，否则就直接将右子树挂在左子树下面。这样时间复杂度是对的。

il void insert(int x) {
	if(!root) {
		val[++tot]=x;
		cnt[tot]++,root=tot;
		maintain(root);
		return;
	}
	int cur=root,f=0;
	while(1) {
		if(val[cur]==x) {
			cnt[cur]++;
			maintain(cur),maintain(f);
			splay(cur);
			break;
		}
		else {
			f=cur;
			cur=ch[cur][val[cur]<x];
			if(!cur) {
				tot++;
				val[tot]=x,cnt[tot]++;
				fa[tot]=f,ch[f][val[f]<x]=tot;
				maintain(tot),maintain(f);
				splay(tot);
				break;
			}
		}
	}
}
il void del(int x) {
	getrank(x);
	if(cnt[root]>1) {
		cnt[root]--;
		maintain(root);
		return;
	}
	if(!ch[root][0]&&!ch[root][1]) {
		clear(root);
		root=0;
		return;
	}
	if(!ch[root][0]) {
		int cur=root;
		root=ch[root][1];
		fa[root]=0;
		clear(cur);
		return;
	}
	if(!ch[root][1]) {
		int cur=root;
		root=ch[root][0];
		fa[root]=0;
		clear(cur);
		return;
	}
	int cur=root;
	int tmp=pre();
	fa[ch[cur][1]]=tmp;
	ch[tmp][1]=ch[cur][1];
	clear(cur);
	maintain(root);
}

$\verb|getrank|\And \verb|kth|$

思路类似，即在 splay 树上二分找答案。

il int getrank(int x) {
	int res=0,cur=root;
	while(1) {
		if(x<val[cur]) cur=ch[cur][0];
		else {
			res+=siz[ch[cur][0]];
			if(x==val[cur]) {
				splay(cur);
				return res+1;
			}
			res+=cnt[cur];
			cur=ch[cur][1];
		}
	}
}
il int getkth(int k) {
	int cur=root;
	while(1) {
		if(ch[cur][0]&&k<=siz[ch[cur][0]]) cur=ch[cur][0];
		else {
			k-=cnt[cur]+siz[ch[cur][0]];
			if(k<=0) {
				splay(cur);
				return val[cur];
			}
			cur=ch[cur][1];
		}
	}
}

$\verb|pre|\And\verb|nxt|$

前驱后继，也很简单。

il int pre() {
	int cur=ch[root][0];
	if(!cur) return cur;
	while(ch[cur][1]) cur=ch[cur][1];
	splay(cur);
	return cur;
}
il int nxt() {
	int cur=ch[root][1];
	if(!cur) return cur;
	while(ch[cur][0]) cur=ch[cur][0];
	splay(cur);
	return cur;
}

然后你就通过了普通平衡树和它的加强版。

维护区间的平衡树及其下放标记问题

什么是维护区间的平衡树

就是可以维护数列了。

在维护区间时，splay 树的优先级按照下标排序，而 $val$ 上存储着对应下标的元素。

唯一特殊的就是取区间操作，不妨我们要取 $[l,r]$，那么我们发现如果我们把 $l-1$ 旋到根，那么右子树的所有点都 $\ge l$；把 $r+1$ 旋到根，那么左子树所有点都 $\le l$。因此我们先将 $l-1$ 旋到根，再将 $r+1$ 旋到点 $l-1$ 的右儿子。这样它们中间的就夹着 $[l,r]$。

为了方便取区间 $[1,n]$（其实也就是方便取节点 $0,n+1$），我们再在平衡树中预插入两个哨兵节点充当 $0$ 号和 $n+1$ 号节点。

怎么进行区间修改

维护区间的平衡树在做区间修改的时候也需要用到懒标记思想，即将操作合并后下传。

但是怎么下传、以及下传的时机问题成了一个坑与细节的点。

下传标记

类比线段树的下传方式。在线段树中，我们在 modify 函数中一旦进入到修改区间就：

首先修改代表此区间的节点的信息使得该节点所维护的信息仍然正确。
修改此节点的懒标记，记录它向儿子节点的标记。

线段树的 push_down 是这样的：

对于两个儿子分别处理：
1. 首先修改代表此区间的节点的信息使得该节点所维护的信息仍然正确。
2. 修改此节点的懒标记，记录它向儿子节点的标记。
然后再将当前节点的标记初始化，取消上面的标记。

我们考虑推演到平衡树中。唯一不同的点是，线段树在访问到一个节点时就会下放标记，而平衡树中下放标记有一个特殊的时机，也就是在 kth 函数中下放。

il int kth(int k) {		//区间平衡树中kth是基础操作之一，目的是寻找当前序列上下标为i的节点编号。
	int cur=root;
	while(1) {
		push_down(cur);		//注意下放标记的时机。访问一个节点先下放标记。
		if(ch[cur][0]&&k<=siz[ch[cur][0]]) cur=ch[cur][0];
		else {
			k-=cnt[cur]+siz[ch[cur][0]];
			if(k<=0) {
				splay(cur,0);
				return cur;
			}
			cur=ch[cur][1];
		}
	}
}

除此之外，所有其他操作都不需要下放标记，因为根据上面懒标记的操作过程我们知道下放标记不会对当前节点维护的信息造成任何影响，因为在 push_down 前该节点的信息已经正确。

然而保证一个节点打标记时此节点维护信息的正确性是一件细致活，需要考虑周全。

我们不妨考虑一个支持反转区间、查询区间最大子段和的平衡树。一个节点需要维护 $5$ 个有关于这些操作的信息（不包含 kth、splay 等其他功能）：

$\mathrm{val}$，该节点对应的序列元素。
$\mathrm{lsum}$，此节点子树对应的区间前缀和最大值。
$\mathrm{rsum}$，该区间后缀和最大值。
$\mathrm{fsum}$，该区间最大子段和。
$\mathrm{tag}$，该区间是否要反转的懒标记。

这些 tag 和线段树维护区间最大子段和的标记很类似（是不是因为维护可合并 tag 的方式只能维护半群信息？），但是线段树可没有维护区间反转的道理。

假设我们要进行一次 reverse 操作，设 $u$ 是对应操作区间的根节点，那么我们肯定需要给这个点打上 $\mathrm{tag}$。但是它维护的信息如何变化呢？

不妨举一个例子：

原序列：1 2 -10 4
lsum=3,rsum=4,fsum=4.
反转序列：4 -10 2 1
lsum=4,rsum=3,fsum=4.

不难发现反转后 $\mathrm{lsum},\mathrm{rsum}$ 交换，而 $\mathrm{fsum}$ 不变。

因此我们在给这个点打标记后要进行 swap(lsum[u],rsum[u]) 操作，以维护该节点信息的正确性。当然了交换儿子节点和维护儿子信息不用多说。

代码是这样的：

il void modify_rev(int u) {
	swap(ch[u][0],ch[u][1]);
	swap(lsum[ch[u][0]],rsum[ch[u][0]]);
	swap(lsum[ch[u][1]],rsum[ch[u][1]]);
	tag_rev[u]^=1;
}
il void rev(int pos,int to) {
	pos++;
	int l=kth(pos-1),r=kth(pos+to);
	splay(l,0),splay(r,l);
	int u=ch[r][0];
    modify_rev(u);
    swap(lsum[u],rsum[u]);
    push_up(r),push_up(l);
}

FHQ-Treap

普通的 treap 是带旋转的，而 FHQ-Treap 是不通过旋转来维护 BST 和 heap 性质的，它通过分裂与合并来维护以上信息。这也使得它天生具有了维护区间的能力。而且很重要的一点是它代码长度非常小。

$\verb|split|$

核心操作之一，将一棵 treap 分裂为两棵。

如图，点内数字是权值，按照权值 $116$ 将原来的平衡树分裂成了新的两棵树，其中第一棵树的权值全部小于等于 $116$，另一棵树则全部大于 $116$。

如何分裂呢？其实很简单。我们记录两棵子树的根节点 $l,r$。在分裂的时候，如果当前节点 $u$ 的权值小于等于 $v$，说明当前节点应被归为左树；同时，由 BST 性质可得 $u$ 左子树所有点权值一定小于等于 $v$，因此整棵左子树一定归属于左树，无需递归分裂。接下来应该去右边递归，同时在右子树中，新划到左边的节点应该接在 $u$ 的右儿子上（因为 $u$ 是当前权值最大的节点），所以递归下传即可。$u$ 权值大于 $v$ 的情况类似。

il void split(int u,int v,int &l,int &r) {
	if(!u) {l=r=0;return;}
	if(val[u]<=v) l=u,split(ch[u][1],v,ch[u][1],r);
	else r=u,split(ch[u][0],v,l,ch[u][0]);
	push_up(u);
}

$\verb|merge|$

将两棵树合并成一棵树，同时维护 BST 和 heap 的性质，要求左树权值必须全部小于右树的权值。

如图点内数值为堆性质键值，将两棵树合并成了一棵新树。

维护方式很简单，类似线段树合并。只需要判定键值的大小关系以确定新的父亲和儿子分别是谁即可。由于右树的权值大于左树，因此可以直接确定左右节点的大小顺序关系。

il int merge(int l,int r) {
	if(l==0||r==0) return l+r;
	if(rnd[l]<rnd[r]) {
		ch[l][1]=merge(ch[l][1],r);
		push_up(l);
		return l;
	}
	else {
		ch[r][0]=merge(l,ch[r][0]);
		push_up(r);
		return r;
	}
}

其他操作就非常好写了。

$\verb|insert|$，$\verb|delete|$ 等其他操作的精巧实现

首先 $\verb|kth|$ 操作没有变，仍然是类似二分的方式。

$\verb|insert|$：将树拆成 $\le v$ 和 $>v$ 两部分，新建一个 $=v$ 的节点，再把三部分按顺序粘起来。

$\verb|delete|$：拆成 $v$ 三部分，合并中间那棵树的根节点左右儿子（相当于是把根节点舍掉了），再按顺序粘起来。

$\verb|getrnk|$：拆成 $<v$ 和 $\ge v$ 两部分，输出左半边的大小，再粘回去。

$\verb|pre|$：拆成 $<v$ 和 $\ge v$ 两部分，输出左半边最大值，再粘回去。

$\verb|nxt|$：拆成 $\le v$ 和 $>v$ 两部分，输出右半边最小值，再粘回去。

实测码量极小，大约是 splay 的 $60\%\sim70\%$。

例题

文艺平衡树

给定一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$，其中 $a_i=i$。

你需要进行 $m$ 次操作，每次操作给定一个区间，你需要将这个区间反转。最后输出最终序列上每个元素的值。

利用平衡树维护，时间复杂度 $O(n\log n)$。

维护数列

你需要维护一个数列，支持以下 $6$ 种操作：

在一个元素后面插入若干个元素。

删除一段区间。

将一段区间内的元素赋为同一个值。

反转一段区间。

求区间和。

查询全局最大子段和。

就是刚才的题。时间复杂度 $O(n\log n)$。

要写一坨东西？

火星人

维护一个字符串 $s$，支持以下 $3$ 种操作：

修改第 $i$ 个字符。

在一个字符后面插入一个新字符。

定义 $s_l$ 表示以第 $l$ 个字符开头的后缀，给定两个下标 $x,y$，求出 $\operatorname{lcp}(s_l,s_r)$，其中 $\mathrm{lcp}$ 是最长公共前缀的长度。

首先假装没有第二个操作，考虑只有修改和查询的时候怎么做。

首先肯定不能动态地维护后缀数组。考虑使用字符串哈希和二分来求解，并且用线段树来维护区间哈希值，时间复杂度 $O(n\log n)$。

由于有插入操作，因此我们用 splay 维护这个东西，时间复杂度不变。

郁闷的出纳员

给定一个常量 $c$，维护一个可重集合，初始为空，支持以下四种操作：

给定一个值 $k$，如果 $k\ge c$ 那么将 $k$ 加入到集合中。

将所有元素的值增加 $k$；

将所有元素的值减少 $k$；

输出集合中第 $k$ 大元素。

每进行一次操作，你都需要将集合中所有小于 $c$ 的元素都删除并统计删除的个数。

我们维护一个变量 $\Delta$ 表示当前所有元素的增加量，那么新加入元素的时候应当加入 $k-\Delta$，同时此时 $c^\prime=c+\Delta$。

那么四种操作分别如下：

插入，判定 $k-\Delta$ 和 $c$ 的大小关系，并插入进平衡树。
增加，让 $\Delta$ 增加 $k$ 并且让 $c$ 减少 $k$。
减少，让 $\Delta$ 增加 $k$ 并且让 $c$ 减少 $k$。紧接着将最小的大于等于 $c$ 的元素旋转到根节点，并且删除左子树。
查询，直接寻找第 $k$ 大并加上 $\Delta$。注意判不存在。

由于一次插入只会插入一个元素，一个元素又最多会被删除一次，所以总时间复杂度是 $O(n\log n)$。

文本编辑器

基本是区间平衡树板子题。

Qinshihuang's Blog

平衡树自学笔记