线段树分治：原理、实现与应用-尧图网络科技

一、什么是线段树分治

线段树分治是一种基于时间维度的离线算法思想，它通过将操作或事件按照时间区间分配到线段树的节点上，然后通过遍历线段树来模拟时间的推进与回溯，从而高效处理具有时间区间属性的问题。

其核心思想是：将每个具有生效时间区间 [l, r] 的操作“挂载”到线段树对应的节点上，然后对线段树进行深度优先遍历（DFS）。在进入一个节点时，执行该节点上挂载的所有操作；在离开该节点时，撤销这些操作的影响（即“回溯”）。这样，当遍历到叶子节点（代表某个具体时刻）时，当前维护的状态就是该时刻下所有生效操作叠加后的结果。

二、算法框架与模板

线段树分治的通用实现框架如下（以 C++ 为例）：

struct Operation { int l, r; // 操作生效的时间区间 [l, r) // ... 其他操作相关数据 }; vector<Operation> opTree[N * 4]; // 线段树节点存储操作列表 int timeMax; // 总时间范围 // 将操作插入到线段树对应节点 void addOperation(int u, int l, int r, int ql, int qr, const Operation &op) { if (ql <= l && r <= qr) { opTree[u].push_back(op); return; } int mid = (l + r) >> 1; if (ql < mid) addOperation(u * 2, l, mid, ql, qr, op); if (qr > mid) addOperation(u * 2 + 1, mid, r, ql, qr, op); } // DFS 遍历线段树，处理操作 void dfs(int u, int l, int r) { // 进入节点：执行该节点所有操作 for (auto &op : opTree[u]) { apply(op); // 应用操作，更新当前状态 } if (r - l == 1) { // 到达叶子节点（时刻 l），处理查询 answerQuery(l); } else { int mid = (l + r) >> 1; dfs(u * 2, l, mid); dfs(u * 2 + 1, mid, r); } // 离开节点：撤销操作（回溯） for (auto &op : opTree[u]) { undo(op); // 撤销操作，恢复状态 } }

三、典型应用场景

1. 动态图连通性

维护一个无向图，边在时间区间 [l, r) 内存在，询问某个时刻图的连通分量数量或两点是否连通。使用可撤销并查集配合线段树分治，复杂度为 O((Q+E) log Q α(N))。

2. 带时间限制的背包问题

物品在特定时间区间内可用，询问某个时刻的背包最优解。将物品按时间区间插入线段树，DFS 时维护当前可用的物品集合进行 DP，回溯时撤销 DP 状态。

3. 离线处理区间赋值问题

有一系列区间赋值操作，每个操作在特定时间区间内生效，询问某个时刻某个位置的值。将操作挂载到线段树，DFS 时使用数据结构（如线段树或平衡树）维护当前赋值情况。

四、关键技巧与优化

可撤销数据结构：并查集、线性基、凸包等数据结构需要支持快速撤销最后一步操作。
时间离散化：将时间点离散化为整数，方便线段树建树。
操作合并：同一节点上的多个操作可以批量处理，减少状态切换开销。
内存优化：使用 vector 存储操作，DFS 结束后及时清空。

五、例题与代码实现

例题：动态图连通性（LOJ #121）

给定一个无向图，边在时间区间内存在，询问某个时刻两个点是否连通。

#include <bits/stdc++.h> using namespace std; struct DSU { vector<int> fa, sz; vector<pair<int, int>> history; DSU(int n) : fa(n), sz(n, 1) { iota(fa.begin(), fa.end(), 0); } int find(int x) { while (fa[x] != x) x = fa[x]; return x; } bool merge(int x, int y) { x = find(x), y = find(y); if (x == y) return false; if (sz[x] < sz[y]) swap(x, y); history.emplace_back(y, fa[y]); fa[y] = x; sz[x] += sz[y]; return true; } void undo() { auto [y, oldFa] = history.back(); history.pop_back(); sz[fa[y]] -= sz[y]; fa[y] = oldFa; } }; struct Edge { int u, v, l, r; }; vector<Edge> edges; vector<pair<int, int>> queries; map<pair<int, int>, int> mp; // 记录边上次出现的时间 vector<vector<int>> tree; vector<int> ans; void add(int u, int l, int r, int ql, int qr, int eid) { if (ql >= r || qr <= l) return; if (ql <= l && r <= qr) { tree[u].push_back(eid); return; } int mid = (l + r) >> 1; add(u * 2, l, mid, ql, qr, eid); add(u * 2 + 1, mid, r, ql, qr, eid); } void dfs(int u, int l, int r, DSU &dsu) { int cnt = 0; for (int eid : tree[u]) { auto &e = edges[eid]; if (dsu.merge(e.u, e.v)) cnt++; } if (r - l == 1) { if (l < queries.size()) { auto [x, y] = queries[l]; ans[l] = (dsu.find(x) == dsu.find(y)); } } else { int mid = (l + r) >> 1; dfs(u * 2, l, mid, dsu); dfs(u * 2 + 1, mid, r, dsu); } while (cnt--) dsu.undo(); } int main() { int n, m, T; cin >> n >> m >> T; for (int i = 0; i < m; i++) { int u, v, l, r; cin >> u >> v >> l >> r; u--; v--; if (l == r) continue; edges.push_back({u, v, l, r}); } int q; cin >> q; queries.resize(q); ans.resize(q); for (int i = 0; i < q; i++) { int x, y; cin >> x >> y; x--; y--; queries[i] = {x, y}; } // 建树 int sz = 1; while (sz < q) sz <<= 1; tree.resize(sz * 2); // 添加边到线段树 for (int i = 0; i < edges.size(); i++) { auto &e = edges[i]; add(1, 0, sz, e.l, e.r, i); } DSU dsu(n); dfs(1, 0, sz, dsu); for (int i = 0; i < q; i++) { cout << (ans[i] ? "Yes" : "No") << "\n"; } return 0; }