均摊期望 $O(m \log^2n+q\log n)$ 的动态加边瓶颈连通块算法
Fabian_feibo · · 算法·理论
引入
题目 【模板】菠萝树 / 动态瓶颈连通块:
维护一个最小生成森林,支持对一个点所在的
\le w 的边组成的连通块的所有点权:
- 打上幺半群标记(原题为乘法和加法);
- 统计交换群总和(原题为加法);
显然 Kruskal 重构树。但题目还要求:
- 动态加入
(u,v,w) 的无向边。强制在线。
是的,你没有看错,这题存在均摊期望的
均摊期望:既有均摊也有期望。期望不依赖输入数据。
起因
算法改进自 CF 博客,介绍一种如何避开 LCT、用“带权并查集”维护加边最小生成树的算法。
最开始以为是非常朴素的算法:和传统的带权并查集一样,用权值势能记录路径信息。可以随便手搓。
直到最近发现自己完全写不出来,严肃学习。发现根本不是“带权并查集”,做法根本不朴素。
transformed MST / T-MST / 层级树的相关概念
假如我们得到一棵最小生成树,就知道了这棵树的瓶颈/层次信息。
这时候最关心的,莫过于最小生成树上两点的最大边。T-MST 指这样一棵由 MST 变换后的无根树:
- 点集不变;
- 连通性不变;
- 任意两点路径上的最大边边权不变。
容易发现,想要得到一棵 T-MST,充分必要条件为对原生成树做若干次这样的变换(不妨称大边小边变换):
几何上,可以直观理解为较大边沿着较小边滑动。
T-MST 和大边小边变换都是很好理解的概念。不仅如此,T-MST 更提供了一种非常直观、同时严谨的结构,形式化地或极能帮助我们形式化地描述无向图的层级信息。(以往瓶颈问题全靠感觉解释的题解,现在都有统一的描述方法了!)
这启发我们,或许能通过合理的变换,在不损失信息维护能力的情况下,快速维护 T-MST 从而得到原图的瓶颈信息。
定义两种有根的、即除根节点外,每个点都有父节点的 T-MST:
- lazy T-MST:同一条祖先后代链,边权不一定按深度递减;
- strict T-MST:同一条祖先后代链,边权严格按照深度递减。可理解为去三度化的 Kruskal 重构树。
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 的父亲; - 若
v 是根则结束。否则,暂时断开v 和原父亲的边,彻底接上(u,v,w) ,然后递归下去。
这部分操作被 CF 原博客称作
但树形态可能不合法,
于是放弃维护 strict T-MST,转而使用宽松的 lazy T-MST,只在需要时恢复结构。根据 T-MST 理论,逆序 / lazy T-MST 并没有损失层次信息,需要时是可以完整还原的。
判断
- 如果
\mathrm{val}_u\ge \mathrm{val}_{p_u} ,路径压缩,或者说进行一次大边小边变换。顺便完成了一次向上跳跃; - 否则
u\leftarrow p_u 。
直到到达根。容易证明算法正确性。
实现见原博客,码量很小。
复杂度分析
原博客未给出复杂度证明,但猜想具有和 LCT 相同复杂度:事实的确如此。并声称常数仅为
GPT 6-Astra 补充了严谨证明。事实上并不难说明 strict T-MST 有
-
考虑变量
x 每一步等概率变为[1,x) 中的任意整数,则n\rightarrow1 期望步数为H_{n-1} ; -
自底向上,按优先级从小到大确定 strict T-MST。具体来说,每次从剩下点中随机选出一点,赋上递增点权,并确定它的所有儿子;
-
假如已确定前
x 个点,第x 个是u ,还有n-x 个点未确定。这时候,无论前x 个点如何排布,u 的父亲一定从一个固定的集合\mathcal A 中均匀选取。这是因为:- 记
C_w(u) 表示u 所在的由\le w 的边组成的连通块,\lambda(u)=\min\{ w | \exists v\in C_w(u),\mathrm{pri}_v>\mathrm{pri}_u\} ,\lambda(u) 不存在记为+\infin ; - 可以推出
\lambda(u)=\mathrm{val}_u ;(很重要也很好用的引理,建议命名为 lambda 引理) - 可以推出
\mathcal A =\left(C_{\lambda(u)}(u) \setminus C_{\lambda(u)-1}(u)\right) \cap\{v | \mathrm{pri}_v>\mathrm{pri}_u\} ,当然也是\mathcal A =C_{\lambda(u)}(u) \cap\{v | \mathrm{pri}_v>\mathrm{pri}_u\} 。
- 记
-
记
k=|\mathcal A| ,并给剩下m=n-x 个点按优先级从低到高从小到大重标号。设随机变量\mathcal J 是\mathcal A 中元素重标号后的最大值,随机变量\mathcal U 均匀取1,m 。此时,对于所有
y\in[1,m] ,均有:\mathbb P[\mathcal J\le y]=\frac {\mathrm C_y^k}{\mathrm C_m^k}=\frac {y\cdot(y-1)\cdots(y-k+1)}{m\cdot(m-1)\cdots(m-k+1)}\le \frac y m =\mathbb P[\mathcal U\le y] -
上式说明任意 strict T-MST 上一点,向上爬祖先的过程,优先级趋向
n 的速度,不慢于随机变量趋向1 的速度。 -
因此任意一点深度
\mathrm{dep}_u 期望地< H_n 。注意我们证明了对于p_u 只在固定集合\mathcal A 中选取、而\mathcal A 只依赖u 的前缀的情况均有期望调和级数界,这被称为随机前缀引理。
由于所有操作只和点的深度有关,故有调和级数上界。
界相当紧:菊花和链都能卡满。
但 light rTMST 维护的是 lazy T-MST,
没有关系,我们还有更强的引理:即便是 lazy T-MST 任意一点的期望深度也有调和级数界。这是因为:
- lambda 引理对 lazy T-MST 同样成立;
-
- 假如存在该集合,设为 $S(u)$; - 设 $G_t$ 表示只看前 $t$ 时刻加入边的图。对应的,有 $C_w^t(u),\lambda_t(u),\mathcal A_t(u)$; - 假如处于当前局面,能给所有点附上 $\mu(u)$ 表示“最近同步时间”,使得 $S(u)=\mathcal A_{\mu(u)}(u)$,那么 $\mu(u)$ 会更新,当且仅当: - $\operatorname{Getroot}(u)$ 使 $u$ 到根的链边权严格递减,即对应 strict T-MST 的同款链,因此 $p_u=\arg\max_{v\in\mathcal A_t(u)}\mathrm{pri}_v$,即 $\mu(u)$ 被更新为当前时刻; - $\operatorname{Helper}$ 的连边会使较低优先级的点 $u$ 的 $\mathrm{val}$ 严格下降,是比原来更优的解,而把 $v$ 接到 $u$ 下面后一定不会继续向 $u$ 上方移动,否则违反 $\operatorname{Helper}$ 的规则,因此 $(u,v)$ 这对儿子父亲对已经充分更新,$v=\arg\max_{v\in\mathcal A_t(u)}\mathrm{pri}_v$,即 $\mu(u)$ 被更新为当前时刻; - $\operatorname{Addedge}$ 若暂时切断路径上的最大边,得到的两个连通块仍是合法表示,再用 $\operatorname{Helper}$ 合并使各个 $\mu$ 更新到当前时刻。 - $\mu(u)$ 始终保持良定义,故归纳成立; - $S(u)$ 始终存在,故归纳成立。 - 这被称为 lazy T-MST 的历史候选集合引理。
- 由随机前缀引理,lazy T-MST 任意一点深度期望
\mathcal O(\log n) ,因此 light rTMST 全算法复杂度正确。
由此我们得到了不依赖 LCT 的单次均摊期望
需要注意的是,对于一般树,任意一点期望深度
- 选取
h=\sqrt{n\log n} 个点连成一条链,其余点全部挂在根节点下; - 每个点期望深度
\mathcal O(\frac{h^2}n+1-\frac h n)=\mathcal O(\log n) ,可惜树高\omega(\log n) 。
不过对于 strict T-MST 和 lazy T-MST 我们都还能取得整棵树
-
设当前揭示到
u ,已揭示的是前缀P ,还有m 个未揭示; -
归纳
\mathbb E[2^{\mathrm{dep}_u} | P]\le m+1 :-
-
$\mathbb E[2^{\mathrm{dep}_u} | P]=2\mathbb E[2^{\mathrm{dep}_{p_u}}|P]\le2\mathbb E[m-\mathcal J+1]\le 2\mathbb E[m-\mathcal U+1]=2\cdot \frac{m(m+1)}{2m}=m+1$。
-
-
故对于任意
u ,\mathbb E[2^{\mathrm{dep}_u}]\le \frac {n+1} 2 ; -
由马尔可夫不等式,
\mathbb P[\mathrm{dep}_u\ge k]=\mathbb P[2^{\mathrm{dep}_u}\ge2^k]\le \frac {\mathbb E[2^{\mathrm{dep}_u}]}{2^k}=\frac{n+1}{2^{k+1}} ; -
整棵树树高
\mathrm{height}=\max \mathrm{dep} ,由联合界\mathbb P[\mathrm{height}\ge k]=\mathbb P[\bigcup_u \{\mathrm{dep}_u\ge k\}]\le \sum_u\mathbb P[\mathrm{dep}_u\ge k]=\frac{n(n+1)}{2^{k+1}} ; -
结合界比较宽松,设
B=\frac{n(n+1)}2,L=\lfloor \log_2B \rfloor ,若k<L 我们取\mathbb P[\mathrm{height}\ge k]\le 1 ; -
由此得到
虽然 light rTMST 各项操作不依赖总体树高,但证个树高估计在别处能有用?
信息维护
研究树的经验告诉我们链和子树要分开看。
首先可以查询链的最大边权。
原作者设计这个数据结构之初,就是为了维护 MSF,所以瓶颈连通块信息维护能力较弱。
应该能做一些单点修改,XX 查询,要求阿贝尔群的信息,吧。
原博客用
优势是加边
哦不是原博客的
full rTMST / 全量定向层级树
再次强调:研究树的经验告诉我们链和子树要分开看。
上文从“两点间最大边权不变”的角度引入 T-MST,事实上 T-MST 也不改变
算法描述
我向 GPT 口胡如下算法:
-
使用 strict T-MST,要求任意时刻,边权严格按照深度递减;
-
仍保留 light rTMST 处理的基本框架;
-
除每个点有指向父亲边的指针外,父亲还用按边权递增的有序表记录儿子。有序表不仅存储儿子指针,还会向下传递标记、向上合并答案。为了潜在的局部优化,使用 splay;
-
合并两棵 rTMST,产生逆序的唯一情况,是
\operatorname{Helper} (或者说\operatorname{Union} )依据随机优先级确定完u 和v 的父子关系后,把v 接在u 下的时候。递归地考虑,我们只需要处理
v 以一条w 的边接上u ,v 的权值\ge w 的儿子如何上浮:- 当前有
s=b+c 个父指针相同的儿子组,将要路过p ,其中b 个儿子留下,c 个儿子继续上移; - 维护有序表:分裂有序表,并和
p 原来的有序儿子表做值域有交并; - 处理父指针:
- 如果
b\le \frac s 2 ,暴力修改b 的父指针; - 否则触发 s/2 优化:将父指针一口气改成
p ,再开个并查集处理。另外c 个儿子继续上浮。
- 如果
- 当前有
-
还有一些精细实现优化:跳过不留下任何儿子的祖先;发生一次 s/2 判别后,
c 个儿子的父指针全部解绑,可直接上移到对应祖先,不再走 s/2 判别流程。 -
有了儿子有序表的加持,查询和修改都变得容易了:
-
-
查询:找出对应连通块,向上拉取所有标记,对应连通块的权值自然就是答案;
-
修改:找出对应连通块,向上拉取所有标记,给对应连通块打标记,再次向上更新答案;
-
所以有序表不仅要存儿子边权、儿子自身,还要记录 tag 和子树聚合信息;
-
由于有点深度保证,直接暴力跳每层。
-
并猜测单次操作具有
查询修改和动态树真的很像啊。
免费版 ChatGPT 写了一版,测试效率十分甚至有九分的好。然而 Astra 分析时,发现:
- 所有点父指针变换次数为
\mathcal O(m\log n) ,m 是加边次数,
所以,暴力修改父指针的写法已经有
如果还用 treap 实现,双对数是满的,成为 direct + treap 写法。
s/2 优化写法的复杂度,至少具有 direct 相同的上界,同样忽略并查集。但 Astra 未能给出准确上界,实验测试倾向于同样具有双对数下界。对父指针修改次数多虑了才有了 s/2,感觉纯纯负优化。
splay 写法的复杂度,至少具有 treap 相同的上界。但 Astra 未能给出准确上界,实验测试倾向于同样具有双对数下界。但是我觉得儿子表合并还有戏。
后来突然想到前后缀儿子不还是个 cluster 吗,直接用 SATT 的 rake tree 实现有序表。复杂度同样不清楚,实验测试没有明显优势。
Astra 研究的时候,随手从 arXiv 拉了一篇 union merge 均摊
复杂度分析
Astra 同样给出了简洁的证明:
-
所有边端点的变换次数的一半,就是所有父指针改变的次数;
-
原图一条
(u,v,w) 的边,充当了连接 T-MST 当中C_{w-1}(u) 和C_{w-1}(v) 的桥,两个端点正好分别是C_{w-1}(u) 和C_{w-1}(v) 中优先级最大的点;(这也很重要,建议命名为 beta 引理)
-
这条边如果插入成功,则会一直存活直到加入一条连接
C_{w-1}(u) 和C_{w-1}(v) 且边权<w 的边; -
这段时间里,
C_{w-1}(u) 和C_{w-1}(v) 只会变大不会减小,但至多加入n 个点; -
经典结论:集合最高优先级元素的变换次数的期望又是调和级数;
-
因此所有边端点变化次数
\mathcal O(m\log n) 。
故全局父指针变化次数有
界同样相当紧,比如一个边权递减的菊花图就能卡满。
如果用 treap 做 union merge:单次 union merge
现在所有操作都能
更进一步,如果使用 splay 实现儿子字典,给每点附上在 strict T-MST 对应的子树大小的虚权重,由加权访问引理,查询修改
所以成功做到了
Astra 证明,上面提及的权值递减菊花图,能卡满 direct treap 写法的两个对数,因此对于 direct treap 双对数是紧界。
但不能卡满 direct splay,s/2 优化。SATT rake tree 没分析。我猜测它们都是
另外找了一圈都没找到,splay 做普普通通的 union merge + split 怎么卡满,不考虑在 full rTMST 中?
测试出来常数只有
\frac 1 {12} ,跑得飞快。有的题还拿了最优解,把可并堆干过去了。
到这里我们也能看出 full rTMST 的复杂度,由较为平行的 父指针修改 和 儿子字典维护 两部分组成,其中儿子字典合并占了大头。
Astra 曾尝试使用均摊
信息维护
严格强于 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 只进行了出色的复杂度分析,没有提出任何新的或有价值的算法。
保证本文
AI reviewed。
full rTMST 的代码虽然能实现,但太懒了没时间写,所以不知道哪里有坑。题目数据同样 AI made。
既然是 AI 写的那就不贴了。
open problem
第一遍想问题的时候并没有本文这么清晰的思路。
虽然算法难点在复杂度分析,证明其实不难理解。
未找到能力等价的数据结构,也没有找到分块以外的、还能做到
如果是重复造轮子,就当作首次引入好了。
完整算法完成于 CSP 前。但还有很多问题没有解决,这里流水账地记一下:
direct splay,s/2 和 SATT rake 的复杂度分析没有满意的结果。
感觉能根据两个关键引理出两道 DP?比如统计给定树形态 strict T-MST 的深度和?
静态场景对 Kruskal 重构树也有很强的竞争力:strict T-MST 树高
另外 New Algorithms ...... 还发明了一种数据结构,叫做 AM-tree,也是有关动态瓶颈连通块。Github 上有实现,感觉并不复杂。完全没读。GPT 读了,大致是复杂度严格的 light rTMST,走的确定性复杂度路线,但做不了 full rTMST 的工作如果理解错了踹我。也许能借鉴思路让 full rTMST 复杂度不依赖期望?
对 full rTMST:殷切希望消去
splay union merge 怎么卡?????不可能是单
light/full rTMST 的删边相当薄弱,不能任意删边。删去两点最大边,应该立马接上一条更小的边才是对的。
所以,哪怕已知 MSF 的操作序列,rTMST 也无法维护。这一点弱于诸多动态树算法。不殷切希望支持任意删边。
update:补充大边小边变换(TW Transformation)定理证明。
明确几个关注点:
- 路径瓶颈不变性:任意两点间路径最大边权不变;
- 连通块瓶颈不变性:
C_w(u) 不变。
显然两者等价(这个真不用证了吧),接着:
- 正着来:TW-T 前后瓶颈性相同。直接验证。
- 反着来:瓶颈性相同的 T-MST 能相互通过 TW-T 转化。
- 证明从连通块瓶颈不变性入手,从小往大加边;
- 根据定义,任意加边时刻,两个 T-MST 连通性应不变,也就是连通块是哪些相同,否则不满足瓶颈连通性不相同;
- 加入一条边,有 TW-T 保证的滑动,端点可以在两个连通块随便选。
每次选成一样的那就对了。
当然你也可以找个 canonical,比如优先级恰为点编号的 strict T-MST,一样的。
update:
后来 GPT 发现了一道很像的题 #7760. 化学实验。原题是点权,这样连通块直接就是子树,所以不需要儿子前缀,不需要儿子字典的 union merge。
哦不是,这么简单,直接归并就行的吗,那边转点再用维护子树的动态树似乎开头那道题就解决了。
神奇的是,根据现在的分析,复杂度和能力都和当前 full rTMST 一比一的相同。
极大地挫伤了我对于 full rTMST 还能继续改进到单次加边