SATT的复杂度证明

· · 算法·理论

SATT

oiwiki：最不推荐阅读，不说明记号的含义、配图与文字不符，缺少触及本质的总结性话语，讲了半天也没能让我理解 SATT 到底在干嘛。

论文哥：非常推荐阅读，讲得非常详实，只是缺少实现方面的细节。

EnofTaiPeople 的 Sone1 题解：虽然语言上有些前后不一致，比如“我看不懂 SATT，觉得是 2log，但是勉强接受 1log 的结论”，还有些事实性错误，比如把 AAAT 当做 1log，还有一些完全没必要的话，比如重工业理论是啥，但如果都忽略掉的话还能提供不错的理解，我最终看这篇搞清楚 SATT 的结构了。

jerry3128 的博客：非常推荐阅读，又详实又有代码参考。

Compress Tree 就相当于 AAAT 维护实链的 Splay，Rake Tree 相当于维护虚儿子的 Splay，但 Rake Tree 实际上是二度的（因为 Rake 只涉及两个簇），虚子树信息都存在叶子上，中间结点起到传递标记与统计信息的功能，所以其实是 Leafy Tree，这就是 EnofTaiPeople 所谓的 Splay Leafy Tree。

所以在会 AAAT 的基础上，只要把维护虚儿子的 Splay 改成 SLT 就是 SATT 了。当然 SLT 单旋时（双旋可以看成两次单旋）为了保证目标结点总是冗余结点的儿子，若目标结点与父亲和爷爷不共线则要跟兄弟交换变得共线。

复杂度证明

回顾 LCT 复杂度证明，这里将势能改为 Top Tree 子树大小，在 Compress Tree 跟 Rake Tree 里双旋的摊还成本都可以放成 3(\phi'(x)-\phi(x))；切换处于 Compress Tree/Rake Tree 的状态的摊还成本放为 1+\phi(x')-\phi(x)，还是可以用轻重边均摊证明这部分总实际成本 O(n+m \log n)。

先假设所有 local splay 都做好了，然后切换虚实边会交换一个 Compress Tree 的根右儿子和一个 Rake Tree 的根的儿子（另一个 Compress Tree 的根），这部分会造成 Rake Tree 的根的势能变化，如果势能增加得太多摊还成本就爆 O(m \log n) 了。实际上不会，考虑结点 x 在 Compress Tree 的根中切换的过程，设 y,z 为 Compress Tree 根的左右儿子，w 为 Rake Tree 根另一个儿子，每次有

\Delta \phi = \log_2(S_z+S_w+1)-\log_2(S_x+S_w+1)\\<\log_2(S_x+S_y+S_z+S_w+2)-\log_2 S_x=\phi(x')-\phi(x)

所以一次 Access 因切换虚实边多出来的势能不超过 \log_2 n，再加上实际成本在其他部分的常数倍以内，\sum s+\Delta \phi = O(m \log n) 还是成立的。

如果维护虚儿子的 Splay 不是 leafy 的会发生什么？当实儿子不存在时就要再 Splay 做平衡树合并了，是不是也能分析出 1log 啊？