May 2, 2024
Top Tree 入门题，久闻大名！今天来挑战（自虐）一下。虽说是 Top Tree 入门题，但是网上大部分代码都是用 AAAT（参见某集训队论文，这个称呼甚至真的只是占位符而不是发明人名字缩写），也就是 Splay 维护虚子树信息的三叉动态树，其实我们之前也是遇到过三叉动态树的，比如：
不过这几个题都不涉及子树修改，所以只需要 access() 的时候顺手维护虚子树的状态即可逃课，而这个题里我们终于不得不直面灾厄了 …
和一般的三叉动态树里我们遇到的状况一样，最难的就是把 access() 过程里的虚实切换讨论清楚。
首先看图。我们增加辅助节点，来维护虚子树组成的 leafy tree，
leafy tree
添加辅助节点的想法，则类似于边分治里面我们强行弄成完全二叉树，不过这里和线段树那种 leafy tree 不同，我们可以直接用 Splay 来维护，因此插入一个新节点非常容易写，然后 …
搜了一圈，感觉 jerry3128 的这篇文章 写的最好，甚至给了四种方法的对比，基本上除了常数部分的复杂度分析都讲得特别清楚了 Orz。
Posted by
xiaodao
Category: 日常
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。