使用线段树优化图构建中的区间连边
引言
在处理图论问题时，当涉及大量区间到点或点到区间的连边操作，直接建图会导致边数爆炸。此时，可以借助线段树结构对建图过程进行优化，将原本的高复杂度操作降至对数级别。本文介绍一种基于两棵辅助线段树的建图优化技术，并结合最短路算法解决典型问题。
核心思想
该方法的核心在于引入两棵虚拟的线段树——"出边树"和"入边树"，分别用于高效实现以下三类操作：
- 从单个点向一个区间内所有点连边（点 → 区间）
- 从一个区间内所有点向单个点连边（区间 → 点）
- 两个区间之间的连边（区间 → 区间），可拆解为上述两种操作组合
若采用朴素方式，一次区间连边可能需要添加 \(O(n^2)\) 条边，而通过线段树优化后，每次操作仅需 \(O(\log n)\) 条边即可完成。
结构设计
出边树（向外扩散）
出边树中，每个非叶子节点代表其对应区间的集合。父节点向子节点连权值为0的边，表示信息可以从父节点传递至子节点。当我们需要从某个点 \(v\) 向区间 \([l, r]\) 连一条权值为 \(w\) 的边时，只需将 \(v\) 连接到出边树中覆盖 \([l, r]\) 的若干线段树节点上，利用树内零权边自动扩展到具体点。
入边树（向内汇聚）
入边树则相反，子节点向父节点连零权边。这样，任意属于某个区间的点都可以通过树内路径上升到对应的区间节点。当要求区间 \([l, r]\) 内所有点向某点 \(u\) 连边时，我们先让这些点通过入边树汇聚到对应节点，再由该节点向 \(u\) 连边。
两棵树的关系
原始图中的每个点 \(i\) 在两棵树中均作为叶子节点存在。即：出边树的叶节点 \(i\) 和入边树的叶节点 \(i\) 都对应原图中的第 \(i\) 个顶点。整个图的顶点集包括原始点和两棵树新增的内部节点。
实现细节
数据结构定义
#include <vector>
#include <queue>
using namespace std;
const int MAX = 400010; // 足够容纳原始点 + 线段树节点
struct Edge {
int to;
long long weight;
};
vector<Edge> graph[MAX];
int nodeCount; // 当前总节点数量，初始为n
构建线段树
分别建立出边树与入边树，树中内部节点编号从 \(n+1\) 开始递增分配。
int leftChild[MAX * 4], rightChild[MAX * 4];
int rootOut, rootIn; // 出边树和入边树的根
// 构建出边树：父节点指向子节点
void buildOut(int& node, int l, int r) {
if (l == r) {
node = l;
return;
}
node = ++nodeCount;
int mid = (l + r) / 2;
buildOut(leftChild[node], l, mid);
buildOut(rightChild[node], mid + 1, r);
// 父节点向左右子节点连零权边
graph[node].push_back({leftChild[node], 0});
graph[node].push_back({rightChild[node], 0});
}
// 构建入边树：子节点指向父节点
void buildIn(int& node, int l, int r) {
if (l == r) {
node = l;
return;
}
node = ++nodeCount;
int mid = (l + r) / 2;
buildIn(leftChild[node], l, mid);
buildIn(rightChild[node], mid + 1, r);
// 子节点向父节点连零权边
graph[leftChild[node]].push_back({node, 0});
graph[rightChild[node]].push_back({node, 0});
}
执行区间连边
利用线段树的区间查询机制，在树上定位对应节点并连接。
// 从点 u 向区间 [L,R] 连权值为 w 的边（使用出边树）
void connectPointToRange(int node, int segL, int segR, int L, int R, int u, long long w) {
if (L <= segL && segR <= R) {
graph[u].push_back({node, w});
return;
}
int mid = (segL + segR) / 2;
if (L <= mid)
connectPointToRange(leftChild[node], segL, mid, L, R, u, w);
if (R > mid)
connectPointToRange(rightChild[node], mid + 1, segR, L, R, u, w);
}
// 从区间 [L,R] 向点 u 连权值为 w 的边（使用入边树）
void connectRangeToPoint(int node, int segL, int segR, int L, int R, int u, long long w) {
if (L <= segL && segR <= R) {
graph[node].push_back({u, w});
return;
}
int mid = (segL + segR) / 2;
if (L <= mid)
connectRangeToPoint(leftChild[node], segL, mid, L, R, u, w);
if (R > mid)
connectRangeToPoint(rightChild[node], mid + 1, segR, L, R, u, w);
}
应用实例：CF786B Legacy
题目要求支持三种操作：
- 单点到单点连边
- 单点到区间连边
- 区间到单点连边
解决方案如下：
- 初始化时，令原始节点数为 \(n\)，然后建立两棵范围为 \([1, n]\) 的线段树
- 对于操作2，调用
connectPointToRange(rootOut, 1, n, l, r, v, w) - 对于操作3，调用
connectRangeToPoint(rootIn, 1, n, l, r, v, w) - 最终在扩展后的图上运行 Dijkstra 算法求最短路
Dijkstra 实现
long long dist[MAX];
bool visited[MAX];
void dijkstra(int start) {
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
fill(dist, dist + MAX, LLONG_MAX);
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (visited[u]) continue;
visited[u] = true;
for (auto &edge : graph[u]) {
int v = edge.to;
long long nd = d + edge.weight;
if (nd < dist[v]) {
dist[v] = nd;
pq.push({nd, v});
}
}
}
}
主流程
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int q, s;
cin >> n >> q >> s;
nodeCount = n;
buildOut(rootOut, 1, n);
buildIn(rootIn, 1, n);
while (q--) {
int op; cin >> op;
if (op == 1) {
int v, u, w; cin >> v >> u >> w;
graph[v].push_back({u, w});
} else if (op == 2) {
int v, l, r, w; cin >> v >> l >> r >> w;
connectPointToRange(rootOut, 1, n, l, r, v, w);
} else if (op == 3) {
int v, l, r, w; cin >> v >> l >> r >> w;
connectRangeToPoint(rootIn, 1, n, l, r, v, w);
}
}
dijkstra(s);
for (int i = 1; i <= n; ++i) {
cout << (dist[i] == LLONG_MAX ? -1 : dist[i]) << ' ';
}
cout << '\n';
return 0;
}
