胡扯AAA树

Problem

要求维护一棵树,在资磁LCT所有操作的同时,进行对子树的修改和查询操作。

Solution

Tarjan提出的解决方案是

黄志翱大神在论文中写的是

看过两篇论文的zky大神说这两者不是完全相同的

所以还是叫它 吧(虽然我确实更喜欢 这个名字)

可以看作是 的一种改进,解决了 不能触及子树的弱点,据说复杂度也是O(nlogn)O(n\log n),只是常数巨大。

上, 维护实链,虚边只能通过虚子树的父指针连接。

上,在维护实链的同时想办法维护子树,就可以达到目的了。

维护子树,显然可以在每个节点上记录一个平衡树存储所有的虚子树的根,在 中切换实边对应在平衡树中的插入删除。然而这样会比较麻烦,因为每个节点同时存在两份数据,修改任意一个必须手动地让另一个同步。

翱犇在论文中给出了一种更巧妙的做法(来源于杜教?),记录四个子节点0,1,2,3,前两个还是维护链,后两个维护虚子树。如果通过某种手段可以让所有虚子树都处于叶节点,就可以直接链接过来而不会产生问题了。

做法和边分治比较类似:加入虚节点,把虚子树根的序列强制转成二叉树,就可以了。

注意的是,为了保证复杂度,维护虚子树的二叉树也需要 ,此时必须 虚节点,转到真节点的下方。 会发现:一个真节点的2,3号子节点,维护的序列是完全不会有联系的,因为都是 到真节点就停止了,不会到另一棵子树。这个不必困惑,因为首先这样做是不会让复杂度退化的,其次这样做可以使得对虚实节点的操作完全一视同仁,可以简化实现。