后缀平衡树

定义

后缀之间的大小由字典序定义，后缀平衡树就是一个维护这些后缀顺序的平衡树，即字符串的后缀平衡树是所有后缀的有序集合。后缀平衡树上的一个节点相当于原字符串的一个后缀。

特别地，后缀平衡树的中序遍历即为后缀数组。

构造过程

对长度为的字符串建立其后缀平衡树，考虑逆序将其后缀加入后缀平衡树。

记后缀平衡树维护的集合为，当前添加的后缀为，则添加下一个后缀就是向中加入（亦可理解为后缀平衡树维护的字符串为，下一步往前加入一个字符）。这一操作其实就是向平衡树中插入节点。

这里使用期望树高为的平衡树，例如替罪羊树或 Treap 等。

做法 1

插入时，暴力比较两个后缀之间的大小关系，从而判断之后是往哪一个子树添加。这样子，单次插入至多比较次，单次比较的时间复杂度至多为，一共。

一共会插入次，所以该做法的时间复杂度存在上界。

做法 2

注意到与的区别仅在于，且已经属于了，可以利用这一点来优化插入操作。

假设当前要比较与两个字符串的大小，且。每次比较时，首先比较两串的首字符。若首字符不等，则两串的大小关系就已经确定了；若首字符相等，那么就只需要判断去除首字符后两字符串的大小关系。而两串去除首字符后都已经属于了，这时候可以借助平衡树求排名的操作来完成后续的比较。这样，单次插入的操作至多。

一共会插入次，所以该做法的时间复杂度存在上界。

做法 3

根据做法 2，如果能够判断平衡树中两个节点之间的大小关系，那么就可以在的时间内完成后缀平衡树的构造。

记表示节点的值。如果在建平衡树时，每个节点多维护一个标记，使得若，那么就可以根据的大小判断平衡树中两个节点的大小。

不妨令平衡树中每个节点对应一个实数区间，令根节点对应。对于节点，记其对应的实数区间为，则，其左子树对应实数区间，其右子树对应实数区间。易证满足上述要求。

由于使用了期望树高为的平衡树，所以精度是有一定保证的。实际实现时也可以用一个较大的区间来做，例如让根对应。

做法 4

其实可以先构建出后缀数组，然后再根据后缀数组构建后缀平衡树。这样做的复杂度瓶颈在于后缀数组的构建复杂度或者所用平衡树一次性插入个元素的复杂度。

删除操作

假设当前添加的后缀为，上一个添加的后缀为。后缀平衡树还支持删除后缀的操作（亦可理解为后缀平衡树维护的字符串为，将开头的删除）。

类似于插入操作，借助平衡树的删除节点操作可以完成删除的操作。