cp-algorithms 凸包优化与李超线段树：从 DP 加速到 O(n log n) 实战指南

<导读> 本文讲解 cp-algorithms 仓库 src/geometry/convex_hull_trick.md 中介绍的两大经典斜率优化技巧：Convex hull trick（凸包优化，CHT）与 Li Chao tree（李超线段树）。它们把形如 $dp_i = \min_{j<i}(a_j \cdot x_i + b_j)$ 的转移从 $O(n^2)$ 加速到 $O(n \log n)$ 或 $O(n \log [C\varepsilon^{-1}])$。读完本文，你将掌握下凸包与法向量查询的几何本质、离线/单调场景下的凸包实现、支持完全在线插入的李超线段树完整代码，以及它们在仓库测试体系中的实际验证方式。

1. 问题背景：城市汽油最短代价行程

考虑一个典型动态规划问题：有 $n$ 座城市，你需要开车从城市 $1$ 到达城市 $n$。出发时油箱为空，每行驶一公里消耗一升汽油；第 $k$ 座城市汽油单价为 $cost_k$，且进入第 $k$ 座城市需缴纳过路费 $toll_k$。城市沿同一条直线按坐标 $x_k$ 升序排列。

最优代价显然可由如下 DP 转移得到：

$$dp_i = toll_i+\min\limits_{j<i}(cost_j \cdot (x_i - x_j)+dp_j)$$

朴素做法对每个 $i$ 枚举所有 $j<i$，复杂度为 $O(n^2)$。观察转移项，将其展开：

$$cost_j \cdot (x_i - x_j)+dp_j = (cost_j) \cdot x_i + (dp_j - cost_j \cdot x_j)$$

若把每一条候选直线记为 $y = k \cdot x + b$，其中 $k = cost_j$、$b = dp_j - cost_j \cdot x_j$，那么问题就归结为：向集合中加入线性函数 $kx+b$，并查询某个点 $x$ 处所有函数取值的最小值。$x$ 的取值域为 $[-C, C]$，其中 $C$ 是可能的最大 $|x_i|$；若 $x_i$ 均为整数则精度 $\varepsilon = 1$。两种主流解法分别对应下文的两节内容。

2. Convex hull trick：用下凸包维护直线集

2.1 几何对偶：直线化为平面点

CHT 的核心思想是维护所有线性函数的下凸包。更便于处理的做法是将直线 $(k;b)$ 视作平面上的点，于是“查询最小值”就转化为：对给定查询点 $(x;1)$，在所有候选点 $(k;b)$ 中找出点积 $k \cdot x + b$ 最小的点。由于该点积恰为 $kx+b$，与原问题完全等价。

可以证明（示意图）：点积最小的点必然位于这些点的下凸包上。原理是：与 $(x;1)$ 点积为常数的点位于一条与 $(x;1)$ 正交的直线上，最优函数对应的是凸包上法线与 $(x;1)$ 方向共线的支撑线所触及的那个顶点；该顶点左右两侧边界的法向量分别指向 $(x;1)$ 的两侧。

因此只需维护凸包上的顶点集合以及每条边的法向量。查询 $(x;1)$ 时，找到与其夹角最接近的法向量，答案就是该边的一个端点。

2.2 适用前提：离线或斜率单调

这一几何方案要求新加入直线的斜率 $k$ 单调，或可离线处理（即先加入全部直线、再回答所有查询）。若要求在线插入且 $k$ 无序，就需要借助 set 等数据结构维护完整凸包，实现复杂度显著上升，本文不展开；一个折中的在线方案是平方根分块：每新增 $\sqrt n$ 条直线，就从头重构一次凸包，从而在在线场景下获得 $O(\sqrt n)$ 级别的摊还代价。

需要指出的是，本节开头的“城市汽油”问题无法用离线 CHT 直接解决——因为 $dp_i$ 依赖前面的答案，天然是在线递推的，必须处理在线查询，这正是李超线段树的用武之地。

2.3 实现：基于 C++ complex 的几何工具

仓库建议使用 C++ 的复数类型 complex<ftype> 表示点，并用重定义 #define x real、#define y imag 增强可读性。核心工具函数为点积与叉积：

typedef int ftype;
typedef complex<ftype> point;
#define x real
#define y imag

ftype dot(point a, point b) {
	return (conj(a) * b).x();
}

ftype cross(point a, point b) {
	return (conj(a) * b).y();
}

其中 dot 通过共轭乘法取实部得到 $a_xb_x + a_yb_y$，cross 取虚部得到 $a_xb_y - a_yb_x$（带符号面积的两倍）。

2.4 插入：维护凸包的逆时针条件

假设加入直线的斜率 $k$ 单调递增，且目标是查询最小值。用向量 hull 保存凸包顶点，向量 vecs 保存每条边的法向量。插入新点时，检查凸包最后一条边的法向量与新点到末点的向量之间的点积：该角必须保持逆时针方向，即法向量（指向凸包内部）与新点向量点积非负；只要不满足，就弹出末尾顶点及其对应边。

vector<point> hull, vecs;

void add_line(ftype k, ftype b) {
    point nw = {k, b};
    while(!vecs.empty() && dot(vecs.back(), nw - hull.back()) < 0) {
        hull.pop_back();
        vecs.pop_back();
    }
    if(!hull.empty()) {
        vecs.push_back(1i * (nw - hull.back()));
    }
    hull.push_back(nw);
}

注意 1i * (nw - hull.back()) 表示把向量 $(nw - hull.back())$ 逆时针旋转 90°，得到指向凸包内部方向的法向量。由于斜率单调，新点只会从右侧影响凸包，因此尾部弹出是安全的。

2.5 查询：二分查找第一个逆时针法向量

查询点 $(x;1)$ 的最小值时，找到凸包上第一条由 $(x;1)$ 看过去呈逆时针方向的法向量，该法向量对应边的左端点即为最优函数。判断向量 $a$ 是否相对 $b$ 不逆时针，只需检查叉积 $[a,b]$ 是否为正：

int get(ftype x) {
    point query = {x, 1};
    auto it = lower_bound(vecs.begin(), vecs.end(), query, [](point a, point b) {
        return cross(a, b) > 0;
    });
    return dot(query, hull[it - vecs.begin()]);
}

这里 lower_bound 借助 cross(a, b) > 0 这一比较器在法向量序列上二分，返回第一个满足条件的迭代器；由于 vecs 的方向随斜率单调变化，二分成立。总复杂度：插入摊还 $O(1)$，查询 $O(\log n)$。

3. Li Chao 树：完全在线的斜率优化

3.1 核心思想：在线段树顶点保存候选函数

李超线段树不依赖斜率单调，可以在线处理任意插入与查询。前提是任意两条候选函数最多相交一次（直线、函数满足单调凹凸性均可）。

做法：在一棵覆盖 $x$ 取值域的线段树中，每个顶点保存一个函数，并保证：从根走到任意叶子 $x$ 的路径上，至少有一个顶点保存的函数是 $x$ 处的最小值。查询时沿路径取最小值即可。

3.2 插入算法：比较端点决定下传方向

设当前位于覆盖半区间 $[l,r)$ 的顶点，其中已保存函数 $f_{old}$，现在插入新函数 $f_{new}$。令 $m=\left\lfloor\tfrac{l+r}{2}\right\rfloor$。两个函数的交点要么在 $[l;m)$ 中，要么在 $[m;r)$ 中。通过比较 $l$ 与 $m$ 处的函数值即可判定：

• 若支配函数在 $l$、$m$ 之间发生变化，则交点位于 $[l;m)$；
• 否则交点位于 $[m;r)$。

对不包含交点的一半区间，把“更低的函数”写入当前顶点——它必然是在 $m$ 点较低的那个函数；随后携带“较高的那个函数”递归进入另一半区间。这样，区间前一半的正确性由当前顶点保证，后一半由递归调用维护。插入与单点查询的复杂度均为 $O(\log [C\varepsilon^{-1}])$。

下图展示了插入新函数时，顶点处新旧直线的相对位置与覆盖关系（示意图）：old 与 new 在分界点相交，分界点右侧 new 成为更优直线，因此 new 被下放到右子树继续处理。

3.3 函数表示与默认值

同 CHT 一样，用 complex<ftype> 表示直线系数 $(k;b)$，评估函数值即点积：

typedef long long ftype;
typedef complex<ftype> point;
#define x real
#define y imag

ftype dot(point a, point b) {
    return (conj(a) * b).x();
}

ftype f(point a,  ftype x) {
    return dot(a, {x, 1});
}

线段树用数组 line 以二叉树（1 为根）方式索引；坐标范围较大或使用浮点 double 时，应改用动态开点线段树。初始化时，所有顶点应保存“默认函数”，例如恒等于 $+\infty$ 的直线 $0x + \infty$，保证首次插入时旧函数永不胜出。

3.4 插入实现

const int maxn = 2e5;

point line[4 * maxn];

void add_line(point nw, int v = 1, int l = 0, int r = maxn) {
    int m = (l + r) / 2;
    bool lef = f(nw, l) < f(line[v], l);
    bool mid = f(nw, m) < f(line[v], m);
    if(mid) {
        swap(line[v], nw);
    }
    if(r - l == 1) {
        return;
    } else if(lef != mid) {
        add_line(nw, 2 * v, l, m);
    } else {
        add_line(nw, 2 * v + 1, m, r);
    }
}

逻辑梳理：

• 若在 $m$ 处新函数更小（mid 为真），则新函数接管当前顶点，swap 后旧函数变成携带的“较优函数”继续下传；
• 若端点处更优状态与中点不同（lef != mid），说明交点落在左半区间，递归左子树；否则递归右子树；
• 递归到叶节点（$r-l==1$）时终止。

3.5 查询实现

查询点 $x$ 的最小值，即沿根到叶子路径逐层比较当前顶点的函数值：

ftype get(int x, int v = 1, int l = 0, int r = maxn) {
    int m = (l + r) / 2;
    if(r - l == 1) {
        return f(line[v], x);
    } else if(x < m) {
        return min(f(line[v], x), get(x, 2 * v, l, m));
    } else {
        return min(f(line[v], x), get(x, 2 * v + 1, m, r));
    }
}

由于路径上某个顶点必然保存了 $x$ 处的最小值，取 min 即可得到全局最小值。整体上，add_line 与 get 均为 $O(\log C)$，且无需斜率单调、支持任意在线插入，这正是它适合“城市汽油”递推 DP 的原因——每个 $i$ 先用 get 查询得到 $dp_i$，再把新直线 $(cost_i, dp_i - cost_i \cdot x_i)$ 插入。

4. 仓库测试验证：代码可直接提取运行

本仓库为文档提供了可执行验证机制，充分说明上述代码是“可直接复制的实现”而非伪代码：

• 文档中以 {.cpp file=...} 标记的代码块会被 <a href="https://link.gitcode.com/i/999d7c8a263517c02d10b87671f04043" target="_blank">test/extract_snippets.py</a> 的正则（`^\s*{.cpp\s+file=(\S+)}$）自动提取为独立 .h头文件：本页三个代码块分别产出lichaotree_line_definition.h、lichaotree_addline.h、lichaotree_getminimum.h`；
• test/test_lichaotree.cpp 将这些头文件组装为完整程序：它用 6 条已知直线 {15,125}, {-1,5000}, {-10,10000}, {50,-2400}, {17,3000}, {0,100}，先把所有顶点用 $0x + 10^9$ 初始化，然后逐条插入、并在 $x \in [0, 1000]$ 上逐一与朴素枚举的 min 结果断言比对（assert(mi == get(x))），完整验证了在线插入与查询的正确性；
• test/test.sh 会先用 python extract_snippets.py 从文档抽取代码，再以 g++ -std=c++17 -fsanitize=undefined -fno-sanitize-recover 编译并运行 test_lichaotree.cpp，用 UndefinedBehaviorSanitizer 捕获整数溢出与越界等未定义行为。

另外，test/test_convex_hull.cpp 与 test/data/convex_hull.h 从经典几何凸包（Graham 扫描与单调链）角度验证了凸包算法的正确性，可作为理解本文“下凸包”维护边界的参照——本文 CHT 的 add_line 本质就是在斜率单调序列上动态维护下凸包。

若想本地复现：在仓库根目录进入 test/，依次运行 python3 extract_snippets.py 与 ./test.sh（需安装 g++，且需将 C++ 标准至少设为 C++17），即可看到测试通过输出。

5. 两种方案选型对比

维度	Convex hull trick	Li Chao 树
在线插入	仅支持斜率单调，或配合分块重构	完全在线，任意顺序
单次插入	摊还 $O(1)$（单调时）	$O(\log C)$
单次查询	$O(\log n)$（法向量二分）	$O(\log C)$
依赖	下凸包 + 法向量几何	线段树（静态数组或动态开点）
适用场景	离线批处理、斜率单调的 DP 转移	在线递推 DP、非单调斜率、动态规划逐层推进

“城市汽油”一类逐层递推、斜率任意的 DP 应首选李超线段树；而可离线、斜率单调或允许分块重构的场景，CHT 常数更小、实现更轻量。

6. 练习题目

原文档推荐的实战题目（覆盖 CHT 与李超线段树的经典应用）：

• Codebreaker - TROUBLES：几行观察后即可归结为 CHT 的简单应用
• CS Academy - Squared Ends：区间划分 DP 的斜率优化
• Codeforces - Escape Through Leaf：树形 DP 上的在线凸包/李超树
• CodeChef - Polynomials：多项式求值的最值查询
• Codeforces - Kalila and Dimna in the Logging Industry：经典斜率优化 DP
• Codeforces - Product Sum：含位置权重的平方项转移优化
• Codeforces - Bear and Bowling 4：最大化目标函数的对称优化
• APIO 2010 - Commando：竞赛真题级斜率优化

7. 小结

• 斜率优化 DP 的本质是把转移项整理成直线 $kx+b$，问题变为“插入直线 + 查询最小值”；
• CHT 把直线对偶为点、维护下凸包与法向量，在离线或斜率单调时以 $O(n \log n)$ 乃至摊还 $O(n)$ 解决问题；
• 李超线段树在线段树顶点保存候选函数、按中点比较分半下传，实现 $O(\log C)$ 的完全在线插入与查询，是递推型 DP 的通用方案；
• 本仓库通过 test/extract_snippets.py 的代码抽取机制和 test/test_lichaotree.cpp 的逐点暴力对拍，验证了文中所给实现的正确性，代码可直接复用。