打开 Codeforces 787 这套题的时候“Legacy”这名字就透着股老派味道结果题面也确实不按套路出牌表面上是单源最短路实际上连边方式会把你直接打懵。一句话概括这道题给你 n 个点和 q 组加边操作其中有两类操作是“一个点连向一个区间”和“一个区间连向一个点”。我最开始想着这不就是 Dijkstra 板子题吗结果一看 n、q 都是 1e5如果按区间里每个点都暴力连边最坏情况边数直接到 1e10跑个锤子。这时候线段树优化建图就该出场了。它是最短路题里处理区间连边的经典套路也是我印象中所有“线段树 图论”模型里最值得吃透的一个。这篇文章我会从题意开始拆把两棵线段树为什么这么建、方向为什么不能搞反、实测哪里有坑全部讲清楚保证你看完能直接照着敲。1. 先看懂 Legacy 在问什么三种连边方式与建图爆炸现场1.1 三种操作的图论含义题目背景很直接有 n 个点一开始没有边然后给你 q 次操作每次操作往图里加边最后从源点 s 出发跑单源最短路。操作一共三种操作类型描述图论含义暴力建边代价1 u v w从 u 向 v 连一条权值为 w 的有向边单点连单点1 条边2 u l r w从 u 向区间 [l, r] 中每个点连一条权值为 w 的有向边单点连区间r - l 1 条边3 l r v w区间 [l, r] 中每个点向 v 连一条权值为 w 的有向边区间连单点r - l 1 条边看上去很简单对吗关键是数据范围。n 和 q 都到 1e5边权非负题目要求输出源点 s 到每个点的最短距离。操作 2 和操作 3 里一个区间可能横跨大半个数组比如 [1, 100000] 这种。如果老老实实为区间内每一个点单独建边单次操作就是 O(n) 条边q 次操作最坏 O(nq) 1e10 级别。不但时间炸空间也直接炸邻接表存 1e10 条边八辈子都不够。1.2 为什么说问题核心在建图而不在最短路这道题有个迷惑性它叫最短路但 Dijkstra 本身没有任何改造难度难点全在建图。换句话说你只要能把这 q 组操作对应的图高效建出来后面就是堆优化 Dijkstra 的常规操作。那问题来了怎么把“一个点连向一个区间里所有点”这种边压缩成少量边还能保证语义不变这里需要引入一个非常自然的想法区间在数据结构里可以被“代表”。线段树维护区间信息的时候任何区间 [l, r] 都能被拆成 O(log n) 个节点而不是 O(r - l 1) 个叶子。如果我们让这些线段树节点真正具备“通道”能力——从某个区间节点出发能访问到它管辖范围内的所有叶子或者从叶子能走到覆盖它的区间节点——那么边数就能从 O(区间长度) 降到 O(log n)。这个思路就是线段树优化建图。我第一次做这题时也觉得“用线段树节点代替区间”是理所当然的但真正动手时才发现光是“线段树内部要加哪些方向的 0 边”这一个问题就能让人绕晕。别急下一节我把这套模型彻底拆开。2. 线段树优化建图的地基两棵树、两种方向、一组 0 边2.1 为什么需要两棵线段树而不是一棵如果你尝试只用一棵线段树去解决这两类区间操作马上会撞上一个矛盾操作 2 是“点连区间”需要从某个叶子点出发到达线段树中代表区间的节点再由区间节点向下传播到目标叶子操作 3 是“区间连点”需要区间内的任意叶子都走得到代表区间的节点再从区间节点出发连向目标点。这两个方向是反的一个要求“叶子 → 区间节点”另一个要求“区间节点 → 叶子”。如果只在一棵树里同时加双向 0 边逻辑会乱而且会产生一批无意义的可达性分析和调试都很难受。正确做法是建两棵线段树分别扮演不同角色。业界习惯把它们叫“出树”和“入树”这个叫法在当前场景里还算直观但很多人第一次接触还是会搞混。我更愿意用两个词来描述一棵管“发散”一棵管“汇聚”。发散树出树内部从父节点指向子节点权值为 0。它的作用是当你从某个节点进入这棵树上的一个区间节点时可以顺着 0 边一路向下走到这个区间覆盖的所有叶子。这正好对应操作 2点 u 连到代表 [l, r] 的区间节点后就等价于连到了区间里每一个原始点。汇聚树入树内部从子节点指向父节点权值为 0。它的作用是当区间内任意一个原始点需要“以区间成员的身份出现”时可以从对应叶子沿着 0 边一路向上走到覆盖它的区间节点。这正好对应操作 3区间 [l, r] 内每个点都能走到代表该区间的节点再通过一条权值为 w 的边走到目标点 v。2.2 一个地铁换乘的比喻我后来给朋友讲这套结构时用过一个比喻出树就像从总站开往各个支线的接驳车你可以买一张票到达某个总站然后免费换乘到总站覆盖的每一个小区间入树就像从各个支线站台回总站的免费班车你站在任意一个站台上都能免费上行到某个总站从总站再付费买一张票一步到达你要去的目标站。这两套班车系统平时互相独立但任意一个原始点既是一个支线站台的“出站口”也是同一站台的“入站口”。只有把这两个口用一条 0 边打通你才能实现“到达这个点之后继续从它出发去下一个地方”的完整路径。这就是下一节要讲的重头戏。借用这个比喻回来看建图你就能明白为什么这两棵树内部边的方向不能乱动出树如果改成子指向父那点进入区间节点后就只能在区间节点内部原地打转永远下不到叶子。入树如果改成父指向子那区间里的叶子就够不到代表区间的节点后续“从区间到点”的边全部白搭。方向反了语义直接崩盘。关于方向很多人只看一眼代码觉得“都是加 0 边方向无所谓”实际跑数据就傻眼。建议你自己动手画一棵小线段树把方向标上去走一遍路径验证比死记代码有效得多。2.3 线段树节点编号与原始点编号的关系搭建这套模型时还有一个容易踩的设计点节点编号怎么分配。常见做法有两种一种是用一个全局计数器给每个线段树节点分配动态 ID另一种是直接拿线段树数组下标作为出树节点编号。我推荐后者因为实现最直接假设线段树用常规的 p、2p、2p1 索引那么出树节点编号就是线段树索引本身入树节点编号统一偏移一个 off 量。叶子节点恰好就是原始点 1..n不需要额外映射。这样设计的好处在于你在处理操作时根本不需要查表操作 2 的起点 u 直接使用原始编号 uupdate 到区间节点 p 时加边 add(u, p, w)操作 3 的终点 v 也直接使用原始编号 v加边 add(p off, v, w)。编号规则统一、清晰、不容易错。后文完整代码里我会继续沿用这套方案。3. “出到入”的转换边少一条 0 边整个图就废了3.1 叶子处的 0 边到底解决什么问题两棵树建好之后还有一个极度关键的细节每个原始点对应的叶子处必须加一条从“出树叶子”到“入树叶子”的 0 边。我先说结论、再解释为什么因为这条边是新手最容易漏的漏掉之后样例大概率都过不了而且报错方式极其隐蔽。考虑操作 3区间 [l, r] 向点 v 连一条权值为 w 的边。建图手段是把 [l, r] 拆成若干个线段树区间节点对每个区间节点 x加一条从入树节点 x off 指向 v 的权值为 w 的边。那么问题来了区间 [l, r] 里的任意点 p通过怎样一条完整路径才能到 v首先p 是一个原始点它最初在“出树叶子 p”这个位置上。它能直接去入树区间节点 x off 吗不行因为入树内部的 0 边是子指向父就算 p 已经是入树叶子 p off也只能向上走到父节点、祖父节点……也就是说p 必须先想办法让自己变成“入树叶子 p off”。而连接两者的正是叶子处这条 0 边add(p, p off, 0)。我在理解这个步骤时曾把这条边误认为是“双向的让 p 可以在两棵树之间来回穿梭”。但仔细分析后你会发现真正必需的只有出到入这一个方向。原因在于本题所有操作的终点我都设计成了原始点 v 对应的出树叶子操作 1 是 add(u, v, w)操作 3 是 add(x off, v, w)。就是说最短路一旦到达了某个原始点的出树叶子这个点就被视为“已到达”而“已到达的点”如果需要继续作为起点出发它本身就在出树侧可以直接引出下一条边。所以并不需要反向的入到出 0 边。3.2 如果漏了这条边路径会被打断在哪里为了让你彻底理解这条 0 边的作用我举一个具体例子。假设 n 8源点 s 2操作先从点 2 向区间 [1, 4] 连权值为 1 的边再从区间 [1, 4] 向点 6 连权值为 100 的边。显然预期最短路应该是 1 100 101点 2 可以先到区间 [1,4] 里的任意点再从任意点出发通过“区间到点”的边到达点 6。现在检查路径操作 2 的建边是 add(2, 代表区间 [1,4] 的出树节点, 1)再通过出树内部父到子的 0 边可以到达 [1,4] 里任意叶子比如点 4。此时我们位于“点 4 的出树叶子”。接下来要用操作 3 的边去点 6。但是操作 3 的边连接的是“入树区间节点 off”和“点 6 的出树叶子”。点 4 的出树叶子如果想走到入树区间节点必须先到“点 4 的入树叶子”也就是走叶子处那条 add(4, 4 off, 0)。如果没有这条 0 边点 4 就永远停在出树这半边而点 4 作为叶子往上走是父指向子方向的反向不可能凭空跳到入树于是整条路径在“点 4 出树叶子”处彻底断掉后面权值为 0 的入树内部边全部用不上。这是整个线段树优化建图里最值得反复确认的一环。我甚至在 AC 之后专门删掉叶子处这条 0 边跑了一次结果 d[6] 直接变成不可达。所以当你发现自己的程序结果偏大或出现 INF 时优先检查这里。4. 完整实现建树、区间加边、Dijkstra 一整套代码4.1 建树代码与编号分配细节先把代码骨架摆出来。我使用出树节点编号 线段树数组下标入树节点编号 出树编号 off 的规则。#include bits/stdc.h using namespace std; const long long INF 0x3f3f3f3f3f3f3f3fLL; struct Edge { int to; long long w; }; vectorEdge g[800010]; int n, q, s; int off; void add(int u, int v, long long w) { if (u v) return; // 自环对最短路无影响但建树时可能产生顺手省略 g[u].push_back({v, w}); } void build(int p, int l, int r) { if (l r) { // 叶子节点原始点编号 l add(l, l off, 0); // 必要的出 - 入转换边 return; } int mid (l r) 1; build(p 1, l, mid); build(p 1 | 1, mid 1, r); // 出树父 - 子 add(p, p 1, 0); add(p, p 1 | 1, 0); // 入树子 - 父 add((p 1) off, p off, 0); add((p 1 | 1) off, p off, 0); }这里有几个点需要解释。第一为什么数组开 800010线段树节点索引理论最大值小于 4 * n当 n 1e5 时出树索引小于 4e5入树整体偏移一个 offoff 我习惯设为 4 * n 5那么入树最大编号大约是 8e5再加上原始点编号也没有额外开销所以 8e5 出头足够。如果你用的是动态 ID 方案记得单独维护总计数。第二我在 add 函数里直接忽略了自环。建树过程中比如某个节点 p 的左右孩子之一如果不存在其实不会发生因为 build 只在存在区间时调用但叶子处 add(l, l off, 0) 在 n 很大时不会撞车。之所以留这个判断是防止线段树区间为空或者某些激进写法把父节点连向不存在的 0 号节点那才是真的灾难。第三入树内部边的写法很多人会写成 add(p off, (p 1) off, 0)这等于把入树建成了父指向子方向反了。你只需要记住一个口诀出树向下入树向上。代码里入树边是“子”指向“父”即 (p 1) off → p off。4.2 区间更新两个递归函数接下来写操作 2 和操作 3 对应的区间更新。本质上就是线段树的区间分解把 [l, r] 拆成 O(log n) 个完整覆盖的节点在每个节点上连边。void update_out(int p, int l, int r, int ql, int qr, int u, long long w) { if (ql l r qr) { add(u, p, w); // 出树区间节点 return; } int mid (l r) 1; if (ql mid) update_out(p 1, l, mid, ql, qr, u, w); if (qr mid) update_out(p 1 | 1, mid 1, r, ql, qr, u, w); } void update_in(int p, int l, int r, int ql, int qr, int v, long long w) { if (ql l r qr) { add(p off, v, w); // 入树区间节点 - v 的出树叶子 return; } int mid (l r) 1; if (ql mid) update_in(p 1, l, mid, ql, qr, v, w); if (qr mid) update_in(p 1 | 1, mid 1, r, ql, qr, v, w); }这两种更新初看几乎长得一样区别只在最终 add 的方向。我强调一下为什么终点是 v 而不是 v off因为在我们的模型里一个点的“到达”最终落点在出树叶子“从这个点继续出发”的起点也是出树叶子。所以让所有入树的边都指向 v 这个出树叶子最短路跑起来最顺。如果你把终点写成 v off也不会立刻出问题因为叶子处有 v off → v 的转换边存在但每次都要多绕一条 0 边逻辑上不够干净。另外注意操作 1 的单点连单点就直接 add(u, v, w)不需要任何线段树参与。等于说普通有向边完全兼容在最短路里。4.3 Dijkstra 主流程与整体复杂度图建好后Dijkstra 就是教科书写法。唯一需要注意的是边权虽然题目没说多少但可以到 1e9 量级路径长度可能累计到 1e14所以 dist 数组必须用 long longINF 要开到 long long 上限附近。long long dist[800010]; bool done[800010]; void dijkstra(int S) { priority_queuepairlong long, int, vectorpairlong long, int, greaterpairlong long, int pq; memset(dist, 0x3f, sizeof(dist)); dist[S] 0; pq.push({0, S}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (done[u]) continue; done[u] true; for (auto e : g[u]) { if (dist[e.to] d e.w) { dist[e.to] d e.w; pq.push({dist[e.to], e.to}); } } } }主函数里按序处理输入即可int main() { scanf(%d%d%d, n, q, s); off 4 * n 5; build(1, 1, n); while (q--) { int op, u, v, l, r; long long w; scanf(%d, op); if (op 1) { scanf(%d%d%lld, u, v, w); add(u, v, w); } else if (op 2) { scanf(%d%d%d%lld, u, l, r, w); update_out(1, 1, n, l, r, u, w); } else { scanf(%d%d%d%lld, l, r, v, w); update_in(1, 1, n, l, r, v, w); } } dijkstra(s); for (int i 1; i n; i) { if (dist[i] INF / 2) printf(-1 ); else printf(%lld , dist[i]); } printf(\n); return 0; }复杂度方面建树新增的 0 边数量是两棵线段树的内部边总数约 4n 级别每次操作 2/3 产生 O(log n) 条边所以总边数 O(n q log n)总点数 O(4n)。堆优化 Dijkstra 跑在 (4n) 个点、约 (n q log n) 条边的图上总复杂度 O((n q log n) log n)在 1e5 的数据下非常宽裕。实测 CF 原题 4 秒时限这个写法轻松通过。5. 实测中的常见坑与验证方法5.1 我踩过的几个典型问题第一是 off 设太小。我当时第一版把 off 直接写成 n觉得 n 挺大够用了结果入树节点编号和出树节点编号大量重合。比如出树节点 p 的编号可能是 200000入树节点 p off 可能是 300000如果 off 不够大两边编号会撞在一起图上就会出现莫名其妙的边dist 全错。标准做法是 off 4 * n 5确保两棵线段树的编号区间完全不重叠。第二是 INF 的取值。用 int 存 DIST 在这题必炸路径可以累加到 1e14 以上。我见过有人开 long long 但 INF 设成 1e9结果某些点真实距离刚好大于 1e9被当成 INF 判断成不可达。INF 一定要开大我用 0x3f3f3f3f3f3f3f3f或者直接 4e18 都行。第三是优先队列的比较。习惯了写 pairlong long, int 时把距离放 first但偶尔手滑存成 pairint, long long距离会被截断成 int然后排序全乱。这种错误比较难发现因为小数据大概率也过数据一大就 WA 得莫名其妙。建议在本地用小数据测试时故意把一条边权改大观察是否还能输出正确距离很快就能暴露这个问题。第四是区间边界递归时写错。update 函数里我习惯先判断 ql l r qr再往下递归。有些人会把条件写成 ql l qr r其实等价但有一次我把 qr 写成了 r导致 [l, r] 外的节点也被覆盖。线段树区间更新这种代码再怎么小心也不过分最好每次写完都对着一个区间 [2, 6] 手推一遍递归调用。5.2 小白最容易懵的“双向 0 边”和“0 环”问题网上很多题解会在叶子处加两条 0 边add(u, u off, 0) 和 add(u off, u, 0)。这样做从图论语义上讲也能跑出正确答案因为 0 环不会让最短路变小Dijkstra 遇到 dist 相等的点自然不会更新。但我个人不推荐加双向原因有两点一是逻辑上没必要。本题所有操作的终点都已经落在出树叶子不存在“到达入树叶子后还需要继续出发”的场景。加双向 0 边只是掩盖了对模型理解的不透彻。二是会带来额外的状态数。每个叶子多一条边总数多 n 条虽然不影响复杂度但会让调试时路径变得更绕。比如你想手动验证一条路径是不是最短发现多了很多种走法比较干扰思路。什么时候需要加双向如果你把普通边的终点也设计成入树叶子例如 add(u, v off, w)那么你就必须依赖 v off → v 这条转换边。这也没问题算是另一种自洽的模型。只是不管选哪一种必须保证整张图的终点一致不要混用。我最开始就是一会儿连 v一会儿连 v off导致路径时通时不通调了老半天。5.3 推荐的对拍方式这种建图题代码本身不难但一旦模型细节理解错样例可能能过、大数据全错。我强烈的建议是写一个暴力版本对拍。具体做法当 n 较小时比如 n 20用邻接矩阵直接把每次操作区间里每个点都连一遍得到一个纯暴力图跑一遍 Dijkstra 得到标准答案再用线段树优化建图跑一遍对比每个点的距离。对拍脚本不需要多复杂随机生成 n、q、操作类型暴力法和优化法各跑一次发现不一致就停。通不过时把数据缩小到 n 4 或 n 5手动把两棵线段树画出来一步步走路径。这个方法帮我抓出过至少三个隐蔽 bug包括一次区间分解时少判了 qr mid 的条件。如果不想写对拍也可以自己构造几组有代表性的数据。比如 n 1 的情况测试边界再比如操作 2 和操作 3 交替出现迫使路径在出树和入树之间反复切换再比如区间恰好覆盖整个 [1, n]看看线段树根节点的边是否正常。覆盖到这几类数据基本就能保证代码的鲁棒性。我在实际做题过程中的体会是线段树优化建图这道题思路本身并不难难的是把方向、编号、终点设计这几件事一次做对。如果你第一次写 WA 了先别急着怀疑 Dijkstra回到建图阶段把每一条边到底是“出树区间节点到叶子”还是“叶子到入树区间节点”搞清楚。尤其记住那句话出树向下发散入树向上汇聚叶子处必须有出到入的转换边。把这个模型吃透后面遇到用线段树处理区间边的其他题目比如涉及二维区间或者可持久化版本的变体你也能很快迁移过去。