在最短路、强连通分量、2-SAT、网络流等图论问题中，边数有时达到 \(O(n^2)\) 甚至 \(O(n^3)\)，成为时间或空间复杂度的瓶颈所在，使用优化建图可以在不影响效果的情况下建出边数更少的图。
线段树优化建图
建图方法
支持以下四种操作：
-
\(u\to v\) 连边
-
\(u\to [l,r]\) 连边
-
\([l,r]\to v\) 连边
-
\([l_1,r_1]\to [l_2,r_2]\) 连边
区间操作想到线段树，可以把区间拆成 \(\log n\) 个线段树上区间。先按照线段树建出两棵树：外向树和内向树。对于所有连入一个区间的操作，将边连向外向树，这代表着连入一个大区间的边在经过外向树边后，也可以连入小区间；对于所有从一个区间连出的操作，将边从内向树连出，这代表着一个小区间在经过外向树的边后，可以连出大区间的边。
为了避免冲突，将外向树的编号从 \(1\) 开始，内向树的编号从 \(4n\) 开始，单个节点的编号从 \(8n\) 开始，且要与两棵树的叶子相连。
区间与区间相连按照上面做法是 \(O(\log^2 n)\) 条边，可以新建两个节点以一条边相连，将边权设置在这条边上。内向树对应区间全部由其中一个节点连入，外向树对应区间全部连到另一个节点，这样就只有 \(O(\log n)\) 条边。
总点数大概在 \(10n\) 左右，总边数是 \(O(m\log n)\) 级别。
例题
CodeForces-786B Legacy *2300
没有区间连区间，建图完跑最短路，复杂度 \(O(n\log n\log (n\log n))\)。
Luogu-P6348 PA2011 Journeys
只有区间连区间，优化建图后跑 01 BFS。
Luogu-P8021 ONTAK2015 Bajtman i Okrągły Robin
二分图最大权匹配，转成费用流模型，把代表时刻的右部点优化建图。
Luogu-P5025 SNOI2017 炸弹
先缩点，注意到每个强连通分量一定是连续区间，那么可以波及的范围也是连续一段区间，只需求出可达的端点，拓扑转移。
缩点过程用线段树优化建图。
前后缀优化建图
建图方法
可以用于连边区间序列的前后缀或树上根链的情况。
对于序列的前后缀，可以对每个节点 \(i\) 新建两个复制节点 \(pre_i,suf_i\)，连边为 \(pre_i\to i,pre_{i-1},suf_i\to i,suf_{i+1}\)，这样当需要连前缀 \([1,i]\) 时，直接同 \(pre_i\) 相连即可，后缀同理。
对于树上根链，直接建内向树，连根链末尾即可。
例题
Luogu-P6378 PA2010 Riddle
2-SAT 模型，第一类边是 \(O(n^2)\) 级的，注意到连边为整个集合除了本身的所有节点，就是一个前缀一个后缀。
Luogu-P6965 NEERC2016 Binary Code
暴力做法是如果存在前缀关系那么连边跑 2-SAT。
注意到在 Trie 树上，前缀关系就是一条根链，考虑先建内向树，设 \(p_{i,0}\) 表示 \(i\) 串 ? 处填 \(0\) 的状态，每个串在 Trie 树结束的位置与相反的状态连边，这样同前缀每个相反状态连边就优化成了之和 Trie 树上父亲连边，前缀的状态同结束位置的相反状态连边同理，这次是外向树。
也有可能两个串结束状态相同，这一部分相当于一个集合连边，序列上前后缀优化就行。
特判没有 ? 造成的影响。