均摊期望 $O(m \log^2n+q\log n)$ 的动态加边瓶颈连通块算法

· · 算法·理论

引入

题目 【模板】菠萝树 / 动态瓶颈连通块:

维护一个最小生成森林,支持对一个点所在的 \le w 的边组成的连通块的所有点权:

  • 打上幺半群标记(原题为乘法和加法);
  • 统计交换群总和(原题为加法);

显然 Kruskal 重构树。但题目还要求:

  • 动态加入 (u,v,w) 的无向边。

强制在线。

是的,你没有看错,这题存在均摊期望的 qn^{o(1)} 做法,并且完全可以实现。

均摊期望:既有均摊也有期望。期望不依赖输入数据。

起因

算法改进自 CF 博客,介绍一种如何避开 LCT、用“带权并查集”维护加边最小生成树的算法。

最开始以为是非常朴素的算法:和传统的带权并查集一样,用权值势能记录路径信息。可以随便手搓。

直到最近发现自己完全写不出来,严肃学习。发现根本不是“带权并查集”,做法根本不朴素。

transformed MST / T-MST / 层级树的相关概念

假如我们得到一棵最小生成树,就知道了这棵树的瓶颈/层次信息。

这时候最关心的,莫过于最小生成树上两点的最大边。T-MST 指这样一棵由 MST 变换后的无根树:

容易发现,想要得到一棵 T-MST,充分必要条件为对原生成树做若干次这样的变换(不妨称大边小边变换):

几何上,可以直观理解为较大边沿着较小边滑动。

T-MST 和大边小边变换都是很好理解的概念。不仅如此,T-MST 更提供了一种非常直观、同时严谨的结构,形式化地或极能帮助我们形式化地描述无向图的层级信息。(以往瓶颈问题全靠感觉解释的题解,现在都有统一的描述方法了!)

这启发我们,或许能通过合理的变换,在不损失信息维护能力的情况下,快速维护 T-MST 从而得到原图的瓶颈信息。

定义两种有根的、即除根节点外,每个点都有父节点的 T-MST:

rTMST / 定向层级树

以定根的 T-MST 为底层结构,快速维护动态加边图的瓶颈连通块信息的数据结构。

原名 rooted T-MST,显然失去了本义。

light rTMST / 轻量定向层级树

即 CF 博客 描述的“带权并查集”。

算法描述

light rTMST 以 lazy T-MST 为底层结构,试图维护后者进而维护 MST。除此之外,每个点额外赋予一个互不相同的随机优先级,要求父节点优先级严格高于儿子节点。

假如 light rTMST 底层的 lazy T-MST,恰为一棵 strict T-MST,那么连通块的最大边,一定连接连通块的根。

如果断开这条边,得到的两个连通块依然是合法表示。因此容易删去连通块的最大边。

如果加入一条边,且两点在同一连通块,则先找到路径上最大值,容易向上爬 LCA 找到。判断能否加入,如果不能,直接丢弃,否则断开后变为不联通的情况。

总之,我们需要合并两个 rTMST 的算法。加入一条 (u,v,w) 的边,且 u,v 不属于同一连通块:

这部分操作被 CF 原博客称作 \operatorname{AddEdgeHelper}。后面简称 \operatorname{Helper} 或对应并查集称 \operatorname{Union}。

但树形态可能不合法,v 中可能有儿子边权 \ge w。

于是放弃维护 strict T-MST,转而使用宽松的 lazy T-MST,只在需要时恢复结构。根据 T-MST 理论,逆序 / lazy T-MST 并没有损失层次信息,需要时是可以完整还原的。

判断 u,v 连通性,本就要分别 \operatorname{Getroot}。尝试在 \operatorname{Getroot} 中选择性路径压缩,来修复到根链的逆序:

直到到达根。容易证明算法正确性。

实现见原博客,码量很小。

复杂度分析

原博客未给出复杂度证明,但猜想具有和 LCT 相同复杂度:事实的确如此。并声称常数仅为 \frac 1 6\sim\frac1 3。我测出来则是稳定的 \frac 1 {20}。

GPT 6-Astra 补充了严谨证明。事实上并不难说明 strict T-MST 有 \mathcal O(\log n) 的期望树高,更具体地说期望地小于 H_n 即第 n 个调和数,因为:

由于所有操作只和点的深度有关,故有调和级数上界。

界相当紧:菊花和链都能卡满。

但 light rTMST 维护的是 lazy T-MST,p_u 不一定为 \arg\max_{v\in\mathcal A_t(u)}\mathrm{pri}_v。

没有关系,我们还有更强的引理:即便是 lazy T-MST 任意一点的期望深度也有调和级数界。这是因为:

由此我们得到了不依赖 LCT 的单次均摊期望 \mathcal O(\log n) 的动态加边 MSF 算法,实现方便,常数贼小。

需要注意的是,对于一般树,任意一点期望深度 \mathcal O(\log n) 并不能得出整棵树深度 \mathcal O(\log n),比如反例:

不过对于 strict T-MST 和 lazy T-MST 我们都还能取得整棵树 \mathcal O(\log n) 的更紧界:

由此得到 \mathcal O(\log n) 的期望树高。比较神奇,这里就不是调和级数界了。

虽然 light rTMST 各项操作不依赖总体树高,但证个树高估计在别处能有用?

信息维护

研究树的经验告诉我们链和子树要分开看。

首先可以查询链的最大边权。

原作者设计这个数据结构之初,就是为了维护 MSF,所以瓶颈连通块信息维护能力较弱。

应该能做一些单点修改,XX 查询,要求阿贝尔群的信息,吧。

原博客用 \operatorname{connect} 和 \operatorname{disconnect} 维护一些简单的信息,但我现在想不通了,那就不写了。总之维护能力不是很强,肯定(?)不能连通块打标记。

优势是加边 \mathcal O(\log n),这是 full rTMST(暂时?)做不到的。

哦不是原博客的 \operatorname{connect}/\operatorname{disconnect} 好像没啥用啊,只能维护数据结构自身的子树信息,而原图上却没有含义。

full rTMST / 全量定向层级树

再次强调:研究树的经验告诉我们链和子树要分开看。

上文从“两点间最大边权不变”的角度引入 T-MST,事实上 T-MST 也不改变 C_w(u)。

算法描述

我向 GPT 口胡如下算法:

并猜测单次操作具有 \mathcal O(\log^2) 的摊还界,忽略并查集。修改查询的双对数界是容易判断的,而如此设计 splay + s/2,是因为通过手玩观察到“兄弟分离难重逢”现象:分离的两个儿子组,很难再次合并为一组,否则会支付较高的代价(我猜的)。

查询修改和动态树真的很像啊。

免费版 ChatGPT 写了一版,测试效率十分甚至有九分的好。然而 Astra 分析时,发现:

所以,暴力修改父指针的写法已经有 \mathcal O(q\log^2n) 的界。具体来说,修正 \operatorname{Helper} 逆序,不需要 s/2 优化,暴力把每个儿子改到对应的正确父亲即可,被称为 direct 写法。

如果还用 treap 实现,双对数是满的,成为 direct + treap 写法。

s/2 优化写法的复杂度,至少具有 direct 相同的上界,同样忽略并查集。但 Astra 未能给出准确上界,实验测试倾向于同样具有双对数下界。对父指针修改次数多虑了才有了 s/2,感觉纯纯负优化。

splay 写法的复杂度,至少具有 treap 相同的上界。但 Astra 未能给出准确上界,实验测试倾向于同样具有双对数下界。但是我觉得儿子表合并还有戏。

后来突然想到前后缀儿子不还是个 cluster 吗,直接用 SATT 的 rake tree 实现有序表。复杂度同样不清楚,实验测试没有明显优势。

Astra 研究的时候,随手从 arXiv 拉了一篇 union merge 均摊 \mathcal O(\log n) 的 mergeable dictionary,试图达到更优复杂度。不知道是啥,GPT 也没写。

复杂度分析

Astra 同样给出了简洁的证明:

故全局父指针变化次数有 \mathcal O(m\log n) 的界。

界同样相当紧,比如一个边权递减的菊花图就能卡满。

如果用 treap 做 union merge:单次 union merge \mathcal O(h\log(1+\frac n h)) 的复杂度,取 \mathcal O(h\log n),容易发现 \operatorname{Addedge} 有 \mathcal O(q\log^2n) 的界。

现在所有操作都能 \mathcal O(\log^2n) 了!

更进一步,如果使用 splay 实现儿子字典,给每点附上在 strict T-MST 对应的子树大小的虚权重,由加权访问引理,查询修改 C_w(u) 的复杂度能用对数望远镜消去一个对数。(和动态树太像了 *2)

所以成功做到了 \mathcal O(\log n) 查询和修改!

Astra 证明,上面提及的权值递减菊花图,能卡满 direct treap 写法的两个对数,因此对于 direct treap 双对数是紧界。

但不能卡满 direct splay,s/2 优化。SATT rake tree 没分析。我猜测它们都是 \mathcal O(m\log^2n+q\log n)。

另外找了一圈都没找到,splay 做普普通通的 union merge + split 怎么卡满,不考虑在 full rTMST 中?

测试出来常数只有 \frac 1 {12},跑得飞快。有的题还拿了最优解,把可并堆干过去了。

到这里我们也能看出 full rTMST 的复杂度,由较为平行的 父指针修改 和 儿子字典维护 两部分组成,其中儿子字典合并占了大头。

Astra 曾尝试使用均摊 \mathcal O(\log n) union merge 的 mergeable dictionary 进一步优化,然而太复杂于是放弃了。

信息维护

严格强于 light rTMST。

能对连通块打 monoid tag,查询连通块交换群和。

总结

命名和来源

本文命名超级混乱,然而这已经是整理后的结果,刚开始研究时那更是超级无敌混乱。

“带权并查集”来自 CF 博客。本文“带权并查集”均带引号。

T-MST 来自 New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications。层级树是我起的 alias。

大边小边变换同样来自这篇文章,但称呼为 Temporal Wedge Transformation。

本文举出的各类性质引理几乎都不来自论文。

lazy T-MST,strict T-MST,rTMST(light & full) 和几个引理均是我起的名字,不是广泛认可的称呼。

另外论文只有 GPT 读了,如果有更规范的命名,或者很牛逼的科技和点子,欢迎补充。

代码和 AI 使用

严重使用 GPT。但比较失望的是,GPT 只进行了出色的复杂度分析,没有提出任何新的或有价值的算法。

保证本文 100\% 人工生成,没有粘贴 AI 生成的任何内容。

AI reviewed。

full rTMST 的代码虽然能实现,但太懒了没时间写,所以不知道哪里有坑。题目数据同样 AI made。

既然是 AI 写的那就不贴了。

open problem

第一遍想问题的时候并没有本文这么清晰的思路。

虽然算法难点在复杂度分析,证明其实不难理解。

未找到能力等价的数据结构,也没有找到分块以外的、还能做到 qn^{o(1)} 的离线算法。欢迎补充比较好的离线算法。

如果是重复造轮子,就当作首次引入好了。

完整算法完成于 CSP 前。但还有很多问题没有解决,这里流水账地记一下:

direct splay,s/2 和 SATT rake 的复杂度分析没有满意的结果。

感觉能根据两个关键引理出两道 DP?比如统计给定树形态 strict T-MST 的深度和?

静态场景对 Kruskal 重构树也有很强的竞争力:strict T-MST 树高 \mathcal O(\log n),所以能对每层或每棵子树干一些暴力一点的事,就像点分树?

另外 New Algorithms ...... 还发明了一种数据结构,叫做 AM-tree,也是有关动态瓶颈连通块。Github 上有实现,感觉并不复杂。完全没读。GPT 读了,大致是复杂度严格的 light rTMST,走的确定性复杂度路线,但做不了 full rTMST 的工作如果理解错了踹我。也许能借鉴思路让 full rTMST 复杂度不依赖期望?

对 full rTMST:殷切希望消去 \operatorname{Addedge} 的一个对数。full rTMST 复杂度同时受限于父指针修改和儿子字典维护。\mathcal O(m\log n) (多半)卡满了父指针修改的界,但儿子字典目前只分析出 \log\sim\log^2,很有前途。上文提及 Astra 曾想用 mergeable dictionary 分析更紧界,但没有做下去。有谁感兴趣吗?

splay union merge 怎么卡?????不可能是单 \log 吧???

light/full rTMST 的删边相当薄弱,不能任意删边。删去两点最大边,应该立马接上一条更小的边才是对的。

所以,哪怕已知 MSF 的操作序列,rTMST 也无法维护。这一点弱于诸多动态树算法。不殷切希望支持任意删边。

update:补充大边小边变换(TW Transformation)定理证明。

明确几个关注点:

显然两者等价(这个真不用证了吧),接着:

每次选成一样的那就对了。

当然你也可以找个 canonical,比如优先级恰为点编号的 strict T-MST,一样的。

update:

后来 GPT 发现了一道很像的题 #7760. 化学实验。原题是点权,这样连通块直接就是子树,所以不需要儿子前缀,不需要儿子字典的 union merge。

哦不是,这么简单,直接归并就行的吗,那边转点再用维护子树的动态树似乎开头那道题就解决了。

神奇的是,根据现在的分析,复杂度和能力都和当前 full rTMST 一比一的相同。

极大地挫伤了我对于 full rTMST 还能继续改进到单次加边 \mathcal O(\log n) 的信心。