比后缀数组还短的后缀平衡树！
zzwdsj
·
2026-10-03 09:18:10
·
算法·理论
:::info[AI使用声明]{open}
本文使用 GPT 辅助文献检索、算法与代码改进、复杂度证明推导及文章检查。
:::
标题中的后缀数组指用倍增和基数排序实现的 O(n\log n) 的算法。
下文默认读者已经掌握普通的重量平衡树维护后缀平衡树。
前言
只想学算法的人可以跳到算法流程部分。
后缀平衡树的一般实现较为复杂的原因是需要写一棵平衡树。
如果能想办法把平衡树换成 std::set/__gnu_pbds::tree，代码会短很多。
替换难点在于底层的平衡树逻辑被封装在内部，无法进行传统的标号。所以我们需要一个全新的标号方式。
显然我是不会的，于是我把这个问题丢给了 GPT。
GPT 找到了这篇论文：
Paul F. Dietz and Daniel D. Sleator. “Two Algorithms for Maintaining Order in a List.” Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC) , 1987, pp. 365–372. PDF。
里面提到的一种算法正好满足要求。
GPT 没找到这个算法的标准译名，暂且叫它平方重标号算法吧。
算法流程
每个节点维护这个节点表示的后缀长度和标号。
先加入一个哨兵节点，长度为 0 ，标号为 0 （实际上哨兵的初始标号是任意的）。
在前面加入一个字符，设新加入的节点为 x 。
设 tag_x 表示 x 的标号，next(x,k) 为平衡树上排在 x 后 k 名的节点。
先把 x 的标号 tag_x 设为 x 的前驱的标号，设前驱的标号为 o 。
因为要处理标号冲突，所以需要给一部分节点重标号。
找到满足 k\ge 1,tag_{next(x,k)}-o> k^2 的最小的 k 。
特别地，如果 k 扫描到末尾仍不满足条件，直接设为 x 与末尾的排名差 +1 。
把 next(x,1),next(x,2),\dots,next(x,k-1) 依次重标号为 o+k,o+2k,\dots,o+(k-1)k 。
把 x 重标号为 o+1 。
正确性证明
只需要证明重标号后标号仍然满足递增。
此时标号是不冲突的。因为当 k>1 时 o+1<o+k ，当 k=1 且后继时 tag_{next(x,k)}-o> k^2=1\iff o+1<tag_{next(x,k)} ，如无后继则无需考虑冲突。
重标号的节点内部显然仍然满足标号递增。
若 k>1 且右边界存在，next(x,k-1) 满足 o+(k-1)k<o+k^2<tag_{next(x,k)} ，k=1 的情况在上面已经讨论。
因此整个序列仍然严格递增。
时间复杂度证明
相邻节点间的正整数间隔 v=tag_{next(x,1)}-tag_x ，定义 \phi(v)=\max(0,\log \frac{n+1}{v}) ，n 为整个操作序列中平衡树中元素个数的最大值。
定义整体势能 \Phi=\sum \phi(g) ，显然非负。
一个引理
先证明一个引理：若正数 g_1,\ldots,g_r 满足
则令 $\rho=\sqrt3/2<1$，有 $\prod_{i=1}^{r}g_i\le \rho^r(r+1)^r$。
:::info[引理的证明]{open}
先考虑 $r$ 为偶数的情况，设 $r=2h$。
$\prod_{i=1}^{r}g_i=\prod_{i=1}^{h}g_i\cdot \prod_{i=h+1}^{2h}g_i$。
对 $\prod_{i=1}^{h}g_i$ 和 $\prod_{i=h+1}^{2h}g_i$ 分别应用均值不等式：
设 $A=\sum_{i=1}^h g_i$，$B=\sum_{i=h+1}^{2h}g_i$。
根据 $\sum_{j=1}^{i}g_j\le i^2(1\le i\le r)$ 有 $A=\sum_{i=1}^h g_i\le h^2$，$A+B=\sum_{i=1}^{2h}g_i\le (2h)^2=4h^2\iff B\le 4h^2-A$。
$\prod_{i=1}^{h}g_i\cdot \prod_{i=h+1}^{2h}g_i\le (\frac{A}{h})^h\cdot(\frac{B}{h})^h\le (\frac{A}{h})^h\cdot(\frac{4h^2-A}{h})^h$。
$(\frac{A}{h})^h\cdot(\frac{4h^2-A}{h})^h=(\frac{A(4h^2-A)}{h^2})^h=(-\frac{A^2}{h^2}+4A)^h$。
二次函数 $f(A)=-\frac{A^2}{h^2}+4A$ 的对称轴为 $2h^2$，故 $f(A)$ 在 $0<A\le h^2$ 单调递增，$-\frac{A^2}{h^2}+4A\le -\frac{h^4}{h^2}+4h^2=3h^2$。
于是 $\prod_{i=1}^{r}g_i\le (3h^2)^h=(\frac{3}{4})^h\cdot (4h^2)^h=(\frac{\sqrt{3}}{2})^{2h}\cdot(2h)^{2h}=\rho^rr^r$。
然后是奇数的情况，设 $r=2h+1$，在序列末尾补上一个 $2r+1$。
$\sum_{i=1}^{r}g_i\le r^2\iff 2r+1+\sum_{i=1}^{r}g_i\le r^2+2r+1=(r+1)^2$，满足条件。
应用偶数的情况得到 $(2r+1)\prod_{i=1}^{r}g_i\le \rho^{r+1}(r+1)^{(r+1)}$。
两边同时除以 $2r+1$：$\prod_{i=1}^{r}g_i\le \rho^r(r+1)^r\cdot\frac{\rho(r+1)}{2r+1}$。因为 $\rho<1$ 且 $r+1\le2r+1$，所以 $\frac{\rho(r+1)}{2r+1}<1$，得到 $\prod_{i=1}^{r}g_i\le \rho^r(r+1)^r\cdot\frac{\rho(r+1)}{2r+1}\le \rho^r(r+1)^r$。
偶数的情况 $\prod_{i=1}^{r}g_i\le \rho^rr^r$，同样满足 $\le \rho^r(r+1)^r$。
:::
#### 势能变化
下面先只讨论 $k>1$ 且右边界存在的情况，其他边界情况需要额外讨论。
设重标号前 $x$ 往后的 $k$ 个间隔为 $g_1,g_2,\dots,g_k$。其中 $g_1$ 是前驱到第一个旧后继的间隙，后续 $g_i$ 是相邻旧后继之间的间隙。如果扫描到末尾则 $g_k$ 不存在。
势能仅在插入前与重标号完成后计算，不在临时标签重复时计算。
根据间隔的定义和算法流程有 $\sum_{j=1}^i g_j=tag_{next(x,i)}-o\le i^2(1\le i <k)$。
根据引理，$\prod_{i=1}^{k-1} g_i \le \rho^{k-1}k^{k-1}$。
##### 内部势能
记 $\Phi_{I}=\sum_{i=1}^{k-1}\phi(g_i)\ge\sum_{i=1}^{k-1}\log\frac{n+1}{g_i}=(k-1)\log (n+1)-\log(\prod_{i=1}^{k-1}g_i)$，这是被重标号的节点内部的旧势能。
重标号后，节点间的间隔为：
$$
\underbrace{1,\ k-1,\ \overbrace{k,\ldots,k}^{k-2\text{ 个} k}}_{k\text{ 个内部间隙}},
$$
根据上面的推导被重标号的节点内部的新势能为 $\Phi'_{I}=k\log(n+1)-\log(\prod_{i=1}^{k}g'_i)=k\log(n+1)-\log(1\cdot(k-1)\cdot k^{k-2})$（因为所有新内部间隙都不超过 $k\le n+1$，所以它们的势能表达式中的 max 可以去掉。）。
相减得到势能变化
$$
\begin{aligned}
\Delta \Phi_I &= \Phi'_I-\Phi_I\\
&\le k\log(n+1)-\log(1\cdot(k-1)\cdot k^{k-2})-(k-1)\log (n+1)+\log\left(\prod_{i=1}^{k-1}g_i\right)\\
&= \log(n+1)+\log\frac{\prod_{i=1}^{k-1}g_i}{(k-1)k^{k-2}}\\
&\le \log(n+1)+\log\frac{\rho^{k-1}k^{k-1}}{(k-1)k^{k-2}}\\
&= \log(n+1)+(k-1)\log \rho+(k-1)\log k-\log(k-1)-(k-2)\log k\\
&= \log(n+1)+(k-1)\log \rho+\log k-\log(k-1)
\end{aligned}
$$
##### 边界势能
接下来计算被重标号的节点与左右边界的势能变化。设 $d=tag_{next(x,k)}-o$。
左边的间隔在上面算过了，旧、新右边界间隙分别为 $R=d-\sum_{i=1}^{k-1}g_i$ 和 $R'=d-(k-1)k$。
$R=d-\sum_{i=1}^{k-1}g_i\ge d-(k-1)^2\ge d-(k-1)k=R'$。
$\Delta \Phi_E=\max(0,\log\frac{n+1}{R'})-\max(0,\log\frac{n+1}{R})\le\log\frac{R}{R'}$（在 $R'\le R$ 时，$\max$ 要么把 $\log\frac{n+1}{R}$ 从负数变为 $0$，要么两个都变为 $0$，不会让差变大）。
$R'-\frac{R}{k}\ge R'-\frac{d}{k}=d-(k-1)k-\frac{d}{k}=(k-1)(\frac{d}{k}-k)\ge 0$。
因此 $R'\ge \frac{R}{k}\implies \frac{R}{R'}\le k$。
故 $\Delta \Phi_E\le \log\frac{R}{R'}\le \log k$。
##### 合并两部分势能
令 $c=-\log\rho=\log\frac2{\sqrt3}>0$。
总势能变化 $\Delta\Phi\le\log(n+1)-c(k-1)+\log k-\log(k-1)+\log k=\log(n+1)-c(k-1)+\log\frac{k}{k-1}+\log k$。
$k>1$ 时，$\frac{k}{k-1}\le 2$，所以 $\log(n+1)-c(k-1)+\log\frac{k}{k-1}+\log k\le \log(n+1)-c(k-1)+\log2+\log k=\log(n+1)-c(k-1)+\log2k$。
因为 $\log(2k)=o(k)$，存在固定常数 $K$，使得当 $k\ge K$ 时，$\log(2k)\le ck/2$。因此 $-c(k-1)+\log(2k)\le-\frac c2k+c$。
对于 $2\le k<K$ 的有限种情况，差额也可以由一个固定常数吸收。因此 $\Delta\Phi\le\log(n+1)-\frac{c}{2}k+O(1)$。
#### 边界情况的势能变化
若 $k=1$ 且没有扫描到末尾（后继存在），$\Delta\Phi=\phi(1)+\phi(d-1)-\phi(d)\le \log(n+1)+\log\frac{d}{d-1}\le \log(n+1)+\log 2$。
若 $k=1$ 且扫描到末尾，势能变化为 $\phi(1)=\log(n+1)$。
若 $k>1$ 且扫描到末尾，没有右边界间隙，只计算内部部分即可，上界仍成立。
#### 删除的势能变化
如果有后继，设要被删除的节点删除前左右间隙的长度为 $g_1,g_2$。
势能变化为 $\phi(g_1+g_2)-\phi(g_1)-\phi(g_2)$。
$\phi$ 非负且单调递减，所以 $\phi(g_1+g_2)\le \phi(g_1)\le \phi(g_1)+\phi(g_2)$。
如果没有后继，设删除的节点删除前左边的间隙为 $g_1$，产生的势能变化为 $-\phi(g_1)\le 0$。
势能不增加，不会产生额外代价，直接按照平衡树删除的 $O(\log n)$ 计算。
#### 时间复杂度
若实际扫描和重标号费用不超过 $Ak$，把势能乘上足够大的常数 $B$，使 $Bc/2\ge A$，有
\text{实际费用}+B\Delta\Phi\le Ak+B\left(\log(n+1)+O(1)-\frac c2k\right)\le B\bigl(\log(n+1)+O(1)\bigr)=O(\log(n+1))
只有哨兵的空集合势能为零。对 $m$ 次操作的摊还费用求和，由最终势能非负，得到扫描和重标号总费用为 $O(m\log(n+1))$。再加上平衡树每次 $O(\log(n+1))$ 的插入、删除费用，总复杂度仍为 $O(m\log(n+1))$。
### 标号范围
容易看出，最大标号的增长是比较快的，因此有必要分析一下标号的范围。
设整个操作序列中平衡树中元素个数的最大值为 $n$，总插入次数为 $m$。
每次产生的标号最大为 $\max(o+1,o+(k-1)k)$，而 $k\le n$，所以每次插入最大标号的增加量不超过 $n^2$。
累计 $m$ 次插入后最大标号增加量不超过 $mn^2$。
最大标号不超过哨兵的初始标号加 $mn^2$，哨兵的初始标号取 $0$ 时，最大标号不超过 $mn^2$。
对于一般 $n,m\le10^6$ 的数据来说 `long long` 足够，保险一点可以开 `__int128`。
### 代码
:::info[P3809 【模板】后缀排序]
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000005;
typedef long long ll;
string s;
ll tag[MAXN];
bool cmp(int x,int y){return s[x]!=s[y]?s[x]<s[y]:tag[x+1]<tag[y+1];}
set<int,decltype(cmp)*>t({0},cmp);
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>s;
int n=s.size();s="*"+s;
for(int i=n;i>=1;i--)
{
auto x=t.insert(i).first,y=next(x);
ll o=tag[*prev(x)];int k=1;
while(y!=t.end()&&tag[*y]-o<=(ll)k*k)y++,k++;
tag[i]=o+1;
for(auto j=next(x);j!=y;j++)o+=k,tag[*j]=o;
}
for(int i:t)if(i)cout<<i<<" ";//if(i)用于跳过哨兵
return 0;
}
```
:::
:::info[P6164 【模板】后缀平衡树]
用一个虚拟的 $-1$ 节点表示查询串。
```cpp
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
const int MAXN=800005;
typedef long long ll;
string s="*",v;
ll tag[MAXN];
bool cmp(int x,int y)
{
if(x==y)return false;
if(x>=0&&y>=0)return s[x]!=s[y]?s[x]<s[y]:tag[x-1]<tag[y-1];
int i=max(x,y),j{};
while(i&&s[i]==v[j])i--,j++;//后缀平衡树维护的是原串的反转
return x<0?v[j]<s[i]:s[i]<v[j];
}
tree<int,null_type,function<bool(int,int)>,rb_tree_tag,tree_order_statistics_node_update>t(cmp);
void add(char c)
{
int i=s.size();s+=c;
auto x=t.insert(i).first,y=next(x);
ll o=tag[*prev(x)];int k=1;
while(y!=t.end()&&tag[*y]-o<=(ll)k*k)y++,k++;
tag[i]=o+1;
for(auto j=next(x);j!=y;j++)o+=k,tag[*j]=o;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int q{},msk{};cin>>q;
cin>>v,t.insert(0);
for(char i:v)add(i);
while(q--)
{
string op{};cin>>op;
if(op[0]=='D')
{
int x{};cin>>x;
while(x--)t.erase(s.size()-1),s.pop_back();
}
else
{
cin>>v;
for(int i=0,j=msk;i<v.size();i++)j=(j*131+i)%v.size(),swap(v[i],v[j]);
if(op[0]=='A')for(char i:v)add(i);
if(op[0]=='Q')
{
reverse(v.begin(),v.end());
int ans=t.order_of_key(-1);
v+='[';
ans=t.order_of_key(-1)-ans;
cout<<ans<<'\n',msk^=ans;
}
}
}
return 0;
}
```
:::