离线动态连通

形式陈述 ​

从操作流生成活跃区间 ​

在离线动态图协议理路动态图算法模型Dynamic graph algorithm model统一图更新序列、查询接口、对手权限以及更新和查询保证。下，固定 $n$ 个带编号顶点，目标是在无向图的 add、remove、query 操作序列上回答连通查询理路图连通性Graph connectivity用顶点间是否存在路径定义无向图的连通性，并由此划分连通分量。，并且全部 $q$ 个操作预先可见。可从空边集开始；若有 $m_0$ 条初始边，则先把它们登记为从时刻零生效。$q=0$ 时没有查询，直接返回空答案列表。以下对 $q\ge 1$ 扫描时间 $0,\dots ,q-1$，对每个带身份的边保存尚未配对的 add 时刻栈；若边没有外部 ID，可用规范端点 (min(u,v), max(u,v)) 作为键，并让栈区分同端点重边。

add 把当前时刻压栈，remove 弹出匹配的 add 时刻并产生半开活跃区间 $[t_{add},t_{remove})$；扫描结束仍未删除的边产生 $[t_{add},q)$。若接口禁止同一边重复激活，第二次 add 应直接报错，不能悄悄覆盖第一次的开始时间。允许平行边或自环的扩展也可按实例处理寿命；其连通查询等价于先去自环、把平行边合成一条后的基础无向可达关系。

把每个活跃区间分解为时间线段树理路线段树Segment tree把区间递归分解为规范节点，并在每个节点保存幺半群聚合值的平衡树结构。的 $O(\log (q+1))$ 个规范节点。节点存放在它所代表的整个时间段内持续活跃的边；一条边可能出现在多个互不重叠的规范节点中，但任一时刻的根叶路径恰好覆盖它一次。

DFS 与回滚不变量 ​

深搜时间树时，进入节点前记录可回滚并查集理路可回滚并查集rollback DSU · undoable union-find把每次合并修改压栈，以快照栈长度为边界撤销最近更新的并查集。快照，再把该节点的所有边 union。到达代表时刻 $t$ 的叶子时，并查集恰含根叶路径上全部边，也就是 $t$ 时的活跃图；此时用 Find 回答 query。离开节点前回滚到快照，保证一个时间分支的边不会泄漏到兄弟分支。

若产生 $a$ 个非空活跃区间，每个区间进入 $O(\log (q+1))$ 个节点；按边实例配对时，$a\le m_0+$ 插入次数。使用按大小合并、无路径压缩的 rollback DSU，Find 与 union 最坏为 $O(\log (n+1))$。计入 DSU 初始化和时间树遍历，主体时间为

预处理的字典成本另计。若边身份已有稠密整数槽位，扫描和配对可线性完成；若需按端点对或任意 ID 建字典，平衡搜索树给出 $O((m_0+q)\log (m_0+q+1))$ 的确定性界，合适随机哈希条件下才可报告期望线性。简写为 $O(q{\log }^{2}q)$ 还需 $n,a=O(q)$、$q\ge 2$ 以及匹配的预处理条件。