OI-wiki 李超线段树（Li Chao Segment Tree）详解：一次函数区间最值的插入、查询与动态开点合并-创锋一号

OI-wiki 李超线段树（Li Chao Segment Tree）详解：一次函数区间最值的插入、查询与动态开点合并

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

李超线段树（Li Chao Segment Tree）是 OI / ICPC 竞赛中用于「动态维护一次函数（直线/线段）在给定横坐标处的最值」的经典数据结构，本指南以其在 OI-wiki 仓库中的核心文档为主体，结合仓库配套实现展开。读完本文，你将掌握李超线段树的引入动机、懒标记下传原理、O(log n)查询与O(log² n)区间插入实现，以及基于动态开点的多树合并技巧。

引入：一个"线段树难以直接维护"的问题

李超线段树解决的问题可以概括为：在平面直角坐标系中动态维护若干线段，支持「插入线段」与「在给定横坐标处查询最高交点」两类操作。

以文档引入的经典例题洛谷 P4097 [HEOI2013] Segment 为例，题目要求维护两个操作（强制在线）：

在平面上加入一条线段，记第 $i$ 条被插入的线段的标号为 $i$，该线段两个端点分别为 $(x_0,y_0)$、$(x_1,y_1)$；
给定一个数 $k$，询问与直线 $x=k$ 相交的线段中，交点纵坐标最大的线段的编号；若有多条线段交点纵坐标并列最大，输出编号最小的；若不存在与给定直线相交的线段，输出 $0$。

数据规模为：操作总数 $1 \le n \le 10^5$，$1 \le k, x_0, x_1 \le 39989$，$1 \le y_0, y_1 \le 10^9$。

传统的线段树维护的是「点的信息」或「可合并的区间信息」，而这里要求维护的是一族函数在某个横坐标处的取值极值，函数之间是竞争关系而非可合并关系，因此传统线段树难以很好地维护这类信息。这种情况下，李超线段树便应运而生。

问题转化：从线段到定义域受限的一次函数

我们可以把上述任务转化为如下等价的抽象操作：

加入一个一次函数 $f(x) = kx + b$，定义域为 $[l, r]$（即一条线段）；
给定 $k$，求所有定义域包含 $k$ 的一次函数中，在 $x = k$ 处取值最大的那个；若有多个函数取值相同，选编号最小的。

注意（垂直线段特判）：当线段垂直于 $x$ 轴时，斜率计算会出现除以零的情况。文档给出的处理方式是：假设线段两端点分别为 $(x, y_0)$ 和 $(x, y_1)$，且 $y_0 < y_1$，则插入定义域为 $[x, x]$ 的一次函数 $f(x) = 0 \cdot x + y_1$。仓库实现 li-chao-tree_1.cpp 中的add函数正是这样处理的：当x0 == x1时，令p[cnt].k = 0, p[cnt].b = max(y0, y1)。

看到"区间修改"，我们自然沿用线段树解决区间问题的常见思路：给每个节点一个懒标记。每个节点 $i$ 的懒标记都是一条线段，记为 $l_i$，表示要用 $l_i$ 来更新该节点所表示的整个区间。

核心过程：懒标记的下传与"只能影响一侧"的性质

现在需要插入一条线段 $f$，考虑某个被新线段 $f$完整覆盖的线段树区间：

若该区间无标记，直接打上用该线段更新的标记；
若该区间已有标记，由于标记难以合并（两条直线的"较优者"随横坐标变化而变化），只能把标记下传。但子节点也有自己的标记，同样可能产生冲突，因此需要递归下传标记。

关键性质在于：按新线段 $f$ 取值是否大于原标记 $g$，可以把当前区间分为两个子区间，其中肯定有一个子区间被左区间或右区间完全包含。也就是说，在两条线段中，肯定有一条线段只可能成为左区间的答案，或者只可能成为右区间的答案。我们用这条线段递归更新对应子树，用另一条线段作为懒标记更新整个区间，这保证了递归下传的复杂度——只有当一条线段只可能成为左或右区间的答案时，它才会被下传，所以不用担心漏掉某些线段。

具体判断规则

设当前区间的中点为 $m$，拿新线段 $f$ 在中点处的值与原最优线段 $g$ 在中点处的值作比较：

若 $f$ 在中点更优，则将 $f$ 与 $g$ 交换，从而始终保证"在中点处 $f$ 不如 $g$ 优"的讨论前提。

在 $f$ 不如 $g$ 优的前提下，分三种情况：

若在左端点处 $f$ 更优：$f$ 和 $g$ 必然在左半区间内产生了交点，$f$ 只有在左区间才可能优于 $g$，递归到左儿子下传；
若在右端点处 $f$ 更优：$f$ 和 $g$ 必然在右半区间内产生了交点，$f$ 只有在右区间才可能优于 $g$，递归到右儿子下传；
若在左右端点处 $g$ 都更优：$f$ 不可能成为答案，无需继续下传。

此外还有一类边界情况：$f$ 和 $g$ 恰好交于中点。程序实现时可以将其归入"中点处 $f$ 不如 $g$ 优"的情况，结果会朝 $f$ 更优的那个端点递归下传。

最终，将 $g$ 作为当前区间的懒标记保存。

实现：插入与下传的核心代码

文档给出如下upd（对线段完全覆盖到的区间进行修改）实现。注意其中引入了浮点数比较函数cmp来处理精度误差：

constexpr double eps = 1e-9; int cmp(double x, double y) { // 因为用到了浮点数，所以会有精度误差 if (x - y > eps) return 1; if (y - x > eps) return -1; return 0; } //... void upd(int root, int cl, int cr, int u) { // 对线段完全覆盖到的区间进行修改 int &v = s[root], mid = (cl + cr) >> 1; int bmid = cmp(calc(u, mid), calc(v, mid)); if (bmid == 1 || (!bmid && u < v)) // 在此题中记得判线段编号 swap(u, v); int bl = cmp(calc(u, cl), calc(v, cl)), br = cmp(calc(u, cr), calc(v, cr)); if (bl == 1 || (!bl && u < v)) upd(root << 1, cl, mid, u); if (br == 1 || (!br && u < v)) upd(root << 1 | 1, mid + 1, cr, u); // 上面两个 if 的条件最多只有一个成立，这保证了李超树的时间复杂度 }

实现细节值得展开说明：

s[root]存储当前节点懒标记线段的编号，calc(u, d)计算编号为u的线段在横坐标d处的取值；
bmid == 1 || (!bmid && u < v)中的后半部分用于处理中点处取值并列的情况——按题目要求选编号更小的线段，这也是仓库源码 li-chao-tree_1.cpp 中原样保留的逻辑；
注释特别强调：上面两个if的条件最多只有一个成立。这正是李超树复杂度的保证——每次下传只会进入一侧子树，不会像普通区间修改那样递归两侧。

插入线段时，需要先定位所有被新线段完整覆盖的区间（区间拆分），再对每个区间调用upd：

void update(int root, int cl, int cr, int l, int r, int u) { // 定位插入线段完全覆盖到的区间 if (l <= cl && cr <= r) { upd(root, cl, cr, u); // 完全覆盖当前区间，更新当前区间的标记 return; } int mid = (cl + cr) >> 1; if (l <= mid) update(root << 1, cl, mid, l, r, u); // 递归拆分区间 if (mid < r) update(root << 1 | 1, mid + 1, cr, l, r, u); }

在 OI-wiki 的数据结构章节中，李超线段树被收录于线段树专题的延伸条目之下，与线段树其他扩展结构（如线段树分治、权值线段树）共同构成完整的区间维护工具集，读者可将本文与 docs/ds/seg.md 对照阅读。

一个重要澄清：懒标记并不等价于"区间中点处取值最大的线段"

文档特别提醒：懒标记并不等价于在区间中点处取值最大的线段。

如图所示，加入黄色线段后，只有红色节点的标记被更新，而绿色节点的标记还未被改变；但在第二、三、四个绿色区间的中点处，显然是黄色线段取值最大。这说明懒标记的选择更多取决于"哪条线段在该区间的优势区间更大"，而非单纯比较中点取值，这也是下传规则要比较两个端点取值的原因。

查询：利用标记永久化思想

查询时，利用标记永久化思想：在包含 $x$ 的所有线段树区间（不超过 $O(\log n)$ 个）的标记线段中，逐一比较得出最终答案，而不必把标记真正下传到叶子。

pdi query(int root, int l, int r, int d) { // 查询 if (r < d || d < l) return {0, 0}; int mid = (l + r) >> 1; double res = calc(s[root], d); if (l == r) return {res, s[root]}; return pmax({res, s[root]}, pmax(query(root << 1, l, mid, d), query(root << 1 | 1, mid + 1, r, d))); }

其中pdi是pair<double, int>的别名，pmax是对该 pair 定义的"先比纵坐标、纵坐标相同时取编号较小者"的取最大值函数，见仓库源码 li-chao-tree_1.cpp。查询路径上的每个节点只需 $O(1)$ 比较，因此单次查询为 $O(\log n)$。

复杂度分析

查询：沿根到叶子的一条路径，比较沿途每个节点的懒标记，时间复杂度显然为 $O(\log n)$；
插入：需要将原线段拆分到 $O(\log n)$ 个完整覆盖的区间中；对于每个区间，又需要花费 $O(\log n)$ 的时间递归下传，因此插入过程的时间复杂度为 $O(\log^2 n)$。

完整参考代码

文档以 HEOI2013 Segment 的完整 AC 代码作为配套实现（docs/ds/code/li-chao-tree/li-chao-tree_1.cpp），仓库源码与文档叙述完全对应，可直接编译运行验证。代码要点如下：

坐标离散范围由MOD1 = 39989与MOD2 = 1000000000定义，与题目数据范围一致；
线段以struct line { double k, b; }存储于数组p[]，s[]为线段树的懒标记（记录线段编号），数组大小按 $4 \times 10^4$ 级别节点预估为160005；
主程序在读入后对输入进行(x + lastans - 1) % MOD + 1的强制在线解码，并通过x0 > x1时交换保证x0 <= x1，随后调用add与update；
查询结果query(1, 1, MOD1, x).second即为满足要求的线段编号，同时作为lastans参与后续输入的在线解码。

扩展：多棵李超线段树的合并（动态开点）

除了单棵树的插入与查询，李超线段树还支持类似普通线段树的合并操作。合并常用于树上统计、DSU on tree、斜率 DP 优化等场景。文档给出如下定义：将两个李超线段树节点 $u, v$ 合并，并以 $u$ 作为新的根：

如果 $v$ 为空，结束过程；
如果 $u$ 为空，将 $v$ 复制给 $u$；
将 $v$ 对应线段插入到以 $u$ 为根的子树；
递归将 $u, v$ 的左右子树对应合并。

由于涉及多棵树的合并，实现需采用动态开点：

void upd(int &root, int cl, int cr, int u) { // 涉及多棵李超线段树合并，使用动态开点． static int idx = 0; if (!root) { s[root = ++idx] = u; return; } int &v = s[root], mid = (cl + cr) >> 1; int bmid = cmp(calc(u, mid), calc(v, mid)); if (bmid == 1 || (!bmid && u < v)) swap(u, v); int bl = cmp(calc(u, cl), calc(v, cl)), br = cmp(calc(u, cr), calc(v, cr)); if (bl == 1 || (!bl && u < v)) upd(ls[root], cl, mid, u); if (br == 1 || (!br && u < v)) upd(rs[root], mid + 1, cr, u); } int merge(int &u, int &v, int l, int r) { if (!u || !v) { return u + v; } if (l == r) { int b = cmp(calc(s[v], l), calc(s[u], l)); if (b == 1 || (!b && s[v] < s[u])) return v; return u; } upd(u, l, r, s[v]); int mid = (l + r) >> 1; ls[u] = merge(ls[u], ls[v], l, mid); rs[u] = merge(rs[u], rs[v], mid + 1, r); return u; }

其中merge中if (!u || !v) return u + v;利用了"空节点编号为 0"的动态开点约定，一次返回非空子树，是线段树合并的经典写法。

复杂度：若合并若干李超线段树涉及的总点数为 $n$，则合并过程复杂度为 $O(n \log n)$。原因是：对于任意线段在树上对应的节点，每次涉及移动它时，要么使其深度 $+1$，要么直接从树上删除，两个操作的代价都是 $O(1)$ 的；而每个节点深度至多为 $O(\log n)$，于是总复杂度即为 $O(n \log n)$。

练习题目

以下是文档收录的经典习题，可用于检验对插入、查询与合并的掌握程度：

「JSOI2008」Blue Mary 开公司（斜率优化与李超树结合的入门题）
「CodeChef」TSUM2 Sum on Tree（树上问题与李超树合并）
「USACO13MAR」Hill Walk G（线段/直线插入的综合应用）
「CF932F」Escape Through Leaf（树上 DP 与李超树合并的经典组合）

建议先独立完成 P4097 [HEOI2013] Segment 的编码，再逐步挑战上述题目，重点体会"编号最小"的并列处理与动态开点合并的边界条件。

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

企业官网建设流程全解析