Suffix Balanced Tree

前言

该算法来源于 2013 年国家集训队论文集中陈立杰的《重量平衡树和后缀平衡树在信息学奥赛中的应用》。
它可以在较优的不依赖于字符集的大小的时间复杂度(一般为 $\mathcal{O}(n\log n)$)内解决后缀自动机、后缀数组的能实现的大部分问题,并且相较于这两种算法更易于理解。同时,后缀平衡树是在线的且同时支持插入和删除操作。
如果使用支持可持久化的平衡树来实现,那么后缀平衡树也能可持久化。

一、重量平衡树

该词的含义并不是十分明确,通常来说,重量平衡树指的是左右子树的大小之比(或其期望)保持在一个有界范围内(一般为不超过某个常数倍)的平衡树,典型的例子是替罪羊树(Scapegoat Tree)、Treap 及其变体等。而红黑树(Red-Black Tree)及其变体、AVL 树等依赖高度平衡的平衡树以及 Spla
y 树等则不是重量平衡树。
根据上述定义可以证明,重量平衡树的期望树高为 $\mathcal{O}(\log n)$,这等价于每个节点有期望 $\mathcal{O}(\log n)$ 个祖先,因此树上一共会有 $\mathcal{O}(n\log n)$ 个形如 “$X$ 是 $Y$ 的祖先”的关系。
从每个 $X$ 的视角考虑,它所对应的每个 $Y$ 即为它子树内的所有点。所以有 $\mathcal{O}(n\log n)$ 个形如 “$X$ 是 $Y$ 的祖先”的关系等价于所有节点的子树大小之和的期望为 $\mathcal{O}(n\log n)$。
根据期望的线性性,所有节点的子树大小的期望之和即亦为 $\mathcal{O}(n\log n)$。
所以每个节点的子树大小的期望为 $\mathcal{O}(\log n)$。

二、后缀平衡树

1. 定义

后缀平衡树的本质就是一棵普通意义下的平衡树,它维护的是单一字符串的全部后缀。
它的每一个节点都代表着该字符串的一个后缀串,其作为二叉搜索树的比较方式是字符串的字典序。
由此不难看出,后缀平衡树的中序遍历就是原字符串的后缀数组。
因此,建出字符串后缀平衡树也是一种求后缀数组的方式。

2. 操作

I. 插入

在后缀平衡树中插入一个节点相当于插入一个后缀。
对于原字符串来说,插入一个后缀等价于在串首插入一个字符。

首先有朴素做法,节点上直接存储后缀,由于期望树高为 $\mathcal{O}(\log n)$,每次插入的时候期望需要 $\mathcal{O}(\log n)$ 次比较,每次比较有需要 $\mathcal{O}(n)$ 的时间复杂度,总复杂度即为 $\mathcal{O}(qn\log n)$,其中 $q$ 为操作次数。
这个做法在时间和空间上都是无法接受的。


当然还有显然的离线做法,即先求出后缀数组,然后直接根据后缀数组值作为后缀的比较依据,不过这样失去了后缀平衡树的很多优势。


考虑将每个节点赋值,形成一个从所有后缀串 $\{s_i\}$ (即所有节点)到某个实数序列 $\{v_i\}$ 的双射,满足 $s_i<s_j\iff v_i<v_j$,然后就可以将后缀串的字典序大小比较转化为 $\mathcal{O}(1)$ 的实数比较。 问题则转化为,如何给节点赋值?
考虑通常画平衡树的方法,如果实现良好,会发现平衡树的每个节点在画面中的“横坐标”的前后就对应着节点在中序遍历中的顺序。
如下图所示。

因此直观地考虑,将平衡树“拍”到线段上,将它视作为类似线段树的结构。
我们让让每个节点 $p$ 管辖一段实数区间 $(l,r)$,然后定义 $v_p=\frac{l+r}{2}$。
对于 $p$ 的左儿子,其管辖区间定义为 $(l,v_p)$,同理右儿子管辖区间为 $(v_p,r)$,即作一次区间对半拆分。特别地,根节点的管辖区间为 $(0,1)$。
在实际代码中,为了避免精度丢失,可以令根节点管辖区间为 $(0,\Omega)$,其中 $\Omega$ 是一个极大的数。
在这种赋值方式下,替罪羊树无疑是最直观的,在重构操作过程中重新计算子树内所有节点的权值 $v$ 即可。
用 Treap 实现亦可,只不过需要额外添加一个重构子树权值的函数并在每次旋转或分裂操作后调用,这种方法期望复杂度是正确的,因为每个节点的子树大小的期望为 $\mathcal{O}(\log n)$。
那么根据这个方法,如何得到插入的算法?
考虑每次插入一个后缀 $s$,等价于在串首插入一个字符 $s_0$,我们先对该字符建立一个新节点,做节点比较的时候先考虑 $s_0$ 是否等于当前节点所代表后缀的首字母 $c$,若 $s_0\neq c$,则直接比较 $s_0$ 和 $c$ 可得这两个后缀的顺序。
否则, $s$ 与以 $c$ 开头的那个后缀的顺序等于它们分别去掉首字符得到的字符串的顺序。而可以发现,这两个被去掉首字符得到的字符串也都是平衡树所维护的字符串的两个后缀,而这两个后缀都已被插入过。既然它们都已被插入过,则说明它们已有自己的权值 (即 $v$),那么直接比较即可。
既然可以 $\mathcal{O}(1)$ 做节点比较,即得到了 $\mathcal{O}(\log n)$ 的插入。

II. 删除


Suffix Balanced Tree
https://cwhirly.github.io/2026/09/04/OI/String/Suffix Structure/Suffix Balanced Tree/
作者
Weihao Cheng
发布于
2026年9月4日
许可协议