算法与数据结构 · 第 19 课

离线动态连通性:时间线段树 × 回滚并查集

2026 年 11 月 7 日|第 3 周 · 第 6 天|讲授约 17 分钟(自测另计)

上节课的 Rollback DSU 只能撤销最近的合并,不能直接删除任意一条旧边。今天把所有加边、删边和查询提前收集,将每条边的“存在时间”分配到时间线段树,再借助 DFS 的进入/退出顺序完成 UNION 与 ROLLBACK。这样就可以回答任意时刻的连通性问题。

一、学习目标与精确模型(约 1 分钟)

学完应能:①把 ADD/REMOVE 配对成边的生存区间;②把时间区间分解成 O(log T) 个线段树节点;③手工跟踪 DFS 的合并、查询和撤销;④用不变量证明正确性;⑤推导时间和空间界并识别重边、时间边界、在线性等限制。

有 n 个顶点(1…n)、T 个按时间编号 t=0,…,T−1 的操作,每个时间点恰好一项:ADD(u,v)、REMOVE(u,v) 或 ASK(u,v)。初始没有边;边是无向、无重边的,保证 ADD 时该边未激活、REMOVE 时它正激活。ASK(t) 问的是执行第 t 项操作后的图。区间统一采用半开形式 [l,r)。

二、为什么不能直接用普通 DSU?(约 2 分钟)

普通并查集只擅长“连通块合并”,不擅长“把已经合并的块拆开”:

ADD(1,2)  → {1,2}、{3}
ADD(2,3)  → {1,2,3}
REMOVE(2,3) → 正确状态应为 {1,2}、{3}

如果只使用普通 UNION,删除时 parent 数组不会自动恢复,ASK(1,3) 会误答连通。

离线方法的关键转换是:不沿真实时间线执行删除。对每条边 e,先算出它在哪些时间存在,即区间 [start(e),end(e));之后做一次“按时间区间组织的 DFS”,进入某个时间范围时加入始终有效的边,离开该范围时撤销。

三、第一步:把操作流变成边的生存区间(约 3 分钟)

例子:n=4,T=8。

t 操作 操作后的关键状态
0 ADD(1,2) 边 1–2 开始存在
1 ADD(2,3) 边 2–3 开始存在
2 ASK(1,3) 两点连通
3 REMOVE(2,3) 边 2–3 不再存在
4 ASK(1,3) 两点不连通
5 ADD(3,4) 边 3–4 开始存在
6 ADD(2,4) 边 2–4 开始存在
7 ASK(1,3) 经 1–2–4–3 连通

对应的边生存区间:

边 生存区间 为什么
(1,2) [0,8) 加入后从未删除
(2,3) [1,3) t=3 执行删除,所以 t=3 已无此边
(3,4) [5,8) 存在到操作序列末尾
(2,4) [6,8) 存在到操作序列末尾

用字典 active[e] 保存尚未删除的边的加入时刻;读到 REMOVE 就生成 [active[e],t),最后仍在 active 中的边统一以 T 为右端点。无向边统一规范化为 (min(u,v),max(u,v))。

MAKE_INTERVALS(ops):
    active = {}
    intervals = []
    for t = 0 .. T-1:
        if ops[t] == ADD(u,v):
            e = normalize(u,v)
            assert e not in active
            active[e] = t
        if ops[t] == REMOVE(u,v):
            e = normalize(u,v)
            assert e in active
            intervals.append((active[e],t,e))
            delete active[e]
    for (e,start) in active:
        intervals.append((start,T,e))
    return intervals

四、第二步:时间线段树不存区间和,而存边(约 3 分钟)

在 [0,T) 上建一棵普通线段树。对边 e 的生存区间 [l,r),把它分解成互不重叠、并集恰好为 [l,r) 的若干整节点区间,并在这些节点的 bucket 中各放一次 e。

例如 T=8:

  • (1,2) 的 [0,8) 放根节点;
  • (2,3) 的 [1,3) 分为 [1,2) 和 [2,3);
  • (3,4) 的 [5,8) 分为 [5,6) 和 [6,8);
  • (2,4) 的 [6,8) 放 [6,8)。
flowchart TD
    R["[0,8):边 (1,2)"] --> A["[0,4)"]
    R --> B["[4,8)"]
    A --> C["[0,2)"]
    A --> D["[2,4)"]
    C --> E["[1,2):边 (2,3)"]
    D --> F["[2,3):边 (2,3)"]
    B --> G["[4,6)"]
    B --> H["[6,8):边 (3,4)、(2,4)"]
    G --> I["[5,6):边 (3,4)"]

图中省略了没有存边的部分叶节点,实际线段树仍覆盖每一个时间点。

对一个连续区间,标准线段树每层最多留下两个“部分覆盖、需要继续展开”的边界节点,因此整段可被 O(1+log T) 个整节点覆盖。设 K 为全部边生存区间的数量,则全部 bucket 共存放 O(K log T) 条“边记录”(T≥2 时)。

ADD_INTERVAL(node, L, R, ql, qr, edge):
    if qr <= L or R <= ql: return
    if ql <= L and R <= qr:
        bucket[node].append(edge)
        return
    M = (L+R)//2
    ADD_INTERVAL(left(node),L,M,ql,qr,edge)
    ADD_INTERVAL(right(node),M,R,ql,qr,edge)

五、第三步:DFS 进入时合并,退出时撤销(约 3 分钟)

这一步直接使用上一课的 Rollback DSU:按大小合并、禁用路径压缩;成功 UNION 记录修改,SNAPSHOT 返回历史栈长度,ROLLBACK(s) 撤销到栈长 s。

DFS(node, L, R):
    s = DSU.SNAPSHOT()
    for (u,v) in bucket[node]:
        DSU.UNION(u,v)

    if R-L == 1:
        if ops[L] == ASK(u,v):
            answer[L] = (DSU.FIND(u) == DSU.FIND(v))
    else:
        M = (L+R)//2
        DFS(left(node),L,M)
        DFS(right(node),M,R)

    DSU.ROLLBACK(s)  # 恢复到刚进入这个节点之前

手工追踪三个查询: 沿 t=2 的根到叶路径,根贡献 (1,2),叶 [2,3) 贡献 (2,3),因此 ASK(1,3) 为真。退出该叶时撤销 (2,3),不会污染 t=4;沿 t=4 的路径只有 (1,2),所以 ASK(1,3) 为假。沿 t=7 的路径,根有 (1,2),[6,8) 再贡献 (3,4) 和 (2,4),因此 ASK(1,3) 为真。

若 history 只记录成功合并:在 t=7 的查询处栈长为 3;离开 [6,8) 时回滚到长度 1;离开根时回滚到 0。DFS 不要求时间顺序是 0→1→2→… 才能正确:它要求的是沿每条根到叶路径,状态能完整进入并恢复。

六、核心不变量与证明(约 2 分钟)

时间覆盖不变量: 每条边 e 的 [l,r) 被精确划成若干互不重叠的线段树节点区间。因此,对于任意时刻 t,e 在 t 活跃,当且仅当从根到叶 t 的路径上恰好有一个节点 bucket 存放 e。

DFS 状态不变量: 在执行某节点的 bucket 以后,DSU 代表的连通关系恰好由当前根到该节点路径上所有 bucket 的边生成。证明按递归深度归纳:根初始空,加入根的边后成立;子节点在继承祖先状态后加入自己的边;退出子节点的 ROLLBACK 精确恢复进入前状态,故另一个兄弟节点不受影响。

在叶 t,路径上的边集合恰好等于时刻 t 的活跃边集合。因此 DSU 的 FIND 同根,恰好等价于原图连通;所有 ASK 都被正确回答。注意证明依赖的是边集合准确 + 回滚准确,不是要求 DSU 的 parent 形状唯一。

七、复杂度、边界与反例(约 2 分钟)

令 K 为边生存区间数、Q 为 ASK 次数、T 为总操作数、n 为顶点数。一个区间分解为 O(log T) 个节点,总 UNION 尝试数为 O(K log T)。Rollback DSU 每次 FIND/UNION 最坏 O(log n),成功合并的撤销为 O(1)。

[ \boxed{\text{总时间 }O(T+K\log T\log n+Q\log n)} ]

[ \boxed{\text{总空间 }O(T+K\log T+n)} ]

这里按 n,T≥2 写;小规模时可把 log 改成 1+log。空间包含时间线段树、bucket、并查集与答案;当前 history 栈至多有 n−1 条成功合并记录,因一条 DFS 路径上的成功合并不可能超过 n−1 次。

不能忽略的边界: ①这是一种离线算法,需要事先知道 REMOVE 的匹配 ADD 和每个查询的时间;②若允许同一 (u,v) 重复加边,须给边加唯一 ID 或维护重数,不能只用一个 active[e];③REMOVE 的时刻不应仍视为边活跃,所以区间右端必须开;④删除某边不能让普通 DSU 自动拆集合,而这里通过退出 DFS 子树撤销;⑤不允许未经日志记录的路径压缩,否则回滚会失真。

八、今日总结与下一课(约 1 分钟)

[ \text{加边/删边事件} \to\text{边的活跃区间} \to\text{时间线段树的 O(log T) 个节点} \to\text{DFS 的 UNION/ROLLBACK} \to\text{每个时刻的连通性答案}. ]

理解这条链,比背复杂度公式更重要:时间线段树决定“哪些边在这一时段有效”,Rollback DSU 决定“进入和离开这一时段时,怎样高效维护连通性”。

下一课(2026-11-08,第 20 课):第 3 周复习。 综合练习 AVL 秩统计、路径复制持久化、Lazy Segment Tree、Rollback DSU 与时间线段树,重点比较各数据结构的不变量、修改范围和历史恢复方式。

九、四级自测(共 100 分;首次不公布答案)

前 3 题可客观判分,Lv4 为开放推导。课堂正文只给中立提示;标准答案、解析与评分细则仅在独立互动测验 JSON 中。

Lv1|时间区间与 DFS 状态|15 分|预计 2 分钟|单选

在离线动态连通性中,把每条边的活跃区间放入时间线段树,DFS 时配合 Rollback DSU。以下哪个判断严格正确?

A. 每访问一个查询叶子都必须重新从头构建整个 DSU,否则祖先状态不可信。

B. 一条边若在时刻 t 活跃,它必须在根到叶 t 的路径上至少出现一次;采用互不重叠的规范区间分解时恰好出现一次,离开节点需回滚其临时合并。

C. REMOVE(u,v) 在时刻 t 执行时,该边仍应包含在 t 的查询状态中,因此它的区间应是 [start,t+1)。

D. 为保证回滚效率,应默认对 FIND 做路径压缩且无需记录压缩造成的 parent 修改。

中立提示:想清楚一个活跃区间如何覆盖叶 t,以及递归进入兄弟子树前应恢复什么状态。

Lv2|操作时间线和连通分量 trace|20 分|预计 4 分钟|数值

有 n=5 个顶点,初始无边,按 t=0…8 执行:0 ADD(1,2);1 ADD(2,3);2 ASK(1,3);3 REMOVE(2,3);4 ADD(4,5);5 ASK(1,5);6 ADD(3,4);7 ADD(2,5);8 ASK(1,3)。求三个 ASK 所在时刻图的连通分量数之和(不是 ASK 返回的布尔值之和)。

中立提示:先在 t=2、5、8 分别列出实际活跃的边;某次 REMOVE 之后,不能继续把该边算进图里。

Lv3|复杂度、快照语义与反例|25 分|预计 4 分钟|多选

设总时间点 T≥2,边生存区间数 K,顶点数 n。关于时间线段树 + 回滚并查集,下列哪些说法成立?(多选)

A. 一个连续的边生存区间能被分解为 O(log T) 个规范线段树节点区间,所以总边记录数为 O(K log T)。

B. 只要 DFS 使用了 SNAPSHOT,退出子树时就可以省略 ROLLBACK,因为之后的兄弟子树一定需要同样的边。

C. 无路径压缩、按大小合并的 DSU 保证 FIND 最坏 O(log n);仅记录成功合并时,一次成功合并可在 O(1) 时间撤销。

D. 若允许同一对端点的多条并行边反复独立增删,仍可不加区分地只用 active[(min(u,v),max(u,v))] 保存唯一的加入时刻。

中立提示:分别审查区间分解上界、兄弟子树之间的状态隔离、DSU 树高,以及同一端点对是否可能存在多个生命周期。

Lv4|算法设计、时间覆盖不变量、复杂度与边界|40 分|预计 10 分钟|开放推导

设计一个离线无向图动态连通性算法:n 个顶点、T 个已知的 ADD/REMOVE/ASK 操作,初始无边,任意时刻每对端点最多一条活跃边,操作合法;ASK(t) 采用操作 t 执行后的状态。(a)(10 分)说明如何把 ADD/REMOVE 匹配为半开生存区间 [l,r),并给出将区间分配到时间线段树规范节点的伪代码;(b)(12 分)给出基于无路径压缩、按大小合并的 Rollback DSU 的 DFS 伪代码,以及叶节点和回溯时的动作;严格证明每个叶 t 的 DSU 连通关系恰好等于时刻 t 的图;(c)(10 分)设 K 为边生存区间数、Q 为查询数,推导总时间 O(T+K log T log n+Q log n) 及额外空间 O(T+K log T+n),解释当前回滚日志为何至多 n−1 条成功合并记录;(d)(8 分)给出普通 DSU 无法直接处理任意删边的具体反例,并讨论删除时刻的右开边界、并行边和不能无日志路径压缩这三种限制。

中立提示:先证明对每条边 e 和时刻 t:e 活跃当且仅当根到叶 t 的路径恰有一个 bucket 存 e;再用 DFS 的快照恢复证明兄弟分支互不污染。复杂度分别计算区间分解、UNION 次数与 ASK。

十、作答与反馈

请回复 Lv1:选项;Lv2:数值与分量划分;Lv3:所有正确选项;Lv4:(a)–(d) 分步推导。按 15/20/25/40 分逐题批改:80–100 分按原计划前进;60–79 分补一道定向题;低于 60 分先复习“活跃区间规范分解 + DFS 回滚不变量”。补练不修改自然日课号。