Skip to main content

进阶算法：线段树分治

Aiden L.7/17/24About 2 min算法算法数据结构线段树分治

什么是线段树分治？

线段树分治是一种离线处理问题的强大技巧。它适用于一类问题：存在一系列操作（或查询），每个操作只在某个时间段内有效。我们无法高效地在线处理这些有时效性的操作，但可以离线地将所有操作和查询读入，然后利用线段树的结构来处理它们。

核心思想

我们将时间轴看作一个大的区间，然后建立一棵线段树。对于每一个有时效性的操作（例如，在时间 [t_start, t_end] 内添加一条边），我们不直接执行它，而是将这个操作“挂”在线段树上对应的 log(T) 个节点上。

具体步骤如下：

  1. 建立时间线段树: 根据总时间范围 [1, T] 建立一棵线段树。
  2. 添加操作: 对于每个在 [t_start, t_end] 时间段内有效的操作，我们在线段树上进行区间更新，将该操作的 ID 添加到完全覆盖 [t_start, t_end] 的线段树节点的列表中。
  3. DFS 遍历: 对整个线段树进行一次深度优先搜索 (DFS)。
    • 当我们进入一个节点时，执行该节点上挂的所有操作（例如，用并查集连接边）。
    • 递归地处理左子节点和右子节点。
    • 当我们离开一个节点时，撤销在该节点上执行的操作，恢复现场（例如，用可撤销并查集断开边）。
    • 如果当前节点是叶子节点，说明我们到达了某个具体的时间点，此时处理该时间点的所有查询。

伪代码

function solve(node, l, r):
  // 应用当前节点的操作
  for op in node.operations:
    apply(op)

  if l == r:
    // 处理时间点 l 的所有查询
    for query in queries_at_time[l]:
      answer(query)
  else:
    mid = (l + r) / 2
    solve(node.left, l, mid)
    solve(node.right, mid + 1, r)

  // 撤销当前节点的操作
  for op in node.operations:
    undo(op)

关键优势

  • 降维: 将一个带时间维度的动态问题，转化为一个离线的、静态的、可以通过 DFS 解决的问题。
  • 适用性广: 常与并查集、凸包、线性基等数据结构结合，解决动态图连通性、动态凸包等复杂问题。
  • 撤销操作: 核心是数据结构必须支持高效的“撤销”操作。可撤销并查集是其经典搭档。

线段树分治是一种优雅的暴力，它用一个 log 的代价，将操作的影响范围精确地分配到各个时间点，是处理带时间区间的离线问题的利器。