Li Chao 直线树 | Codeboy's Blog

形式陈述

如果直线以任意斜率顺序到来，查询横坐标也会前后跳动，怎样动态求出所有已插入直线在 $x$ 处的最小值？Li Chao 树利用“两条直线最多交一次”，把竞争范围递归缩小。

本页采用有限离散坐标版。事先给出 $q\ge1$ 个严格递增的查询坐标 $X=(x_0,\ldots,x_{q-1})$ ，支持插入定义在全部这些点上的仿射函数 $L(x)=mx+b$ ，以及查询任意 $x_i$ 。系数与查询坐标取自实数，比较按精确值解释。树的区间按坐标下标划分，而不是按坐标值等距划分。

每个二叉树结点管理半开下标区间 $[l,r)$ ，取 $h=\lfloor(l+r)/2\rfloor$ ，保存至多一条线。比较线时按二元组 $(L(x),\operatorname{id}(L))$ 排序，值相同选较小编号。插入新线 $g$ ，当前线为 $f$ ：

空结点直接存 $g$ 并结束。
在交换前记录 $u=[g(x_l)<f(x_l)]$ 、 $v=[g(x_h)<f(x_h)]$ ，这里小于包含上述编号平局规则。
若 $v$ 为真，交换 $f,g$ ，使结点留下中点较优的线。
若区间只有一个坐标，结束。否则当 $u\ne v$ 时，把剩余线送入左孩子 $[l,h)$ ；当 $u=v$ 时，送入右孩子 $[h,r)$ 。

查询 $x_i$ 时，沿包含下标 $i$ 的根到叶路径，计算路径上每条存储线的值，取最优二元组。空结构查询返回无候选，数值约定为 $+\infty$ 。这种区间骨架与线段树相似，但结点内容不是子区间数值的聚合。

直觉

两条线的差仍是一条仿射函数，因此其正负至多改变一次。中点较差的线可能在左边翻盘，也可能在右边翻盘，却不可能在两边都翻盘。结点保留中点胜者后，只需把另一条线送到仍可能有优势的一边。

交换前的左右比较给出方向：新线在左端与中点的胜负不同，交接发生在左半；胜负相同，交换后的输家若还能获胜，只可能在右半。即使输家实际上哪里都不赢，继续沿这一半插入也只多花一条路径，不影响正确性。

不变量是：每条已插入线在任意查询点 $x_i$ 的潜在贡献，或者仍由根叶路径上的某条存储线代表，或者已经被路径上的线以更优二元组压住。把输家送往另一半时，当前赢家在被排除的半边始终不差；若这个赢家将来又被替换，同样的支配关系会继续沿查询路径传递。因此路径最小值不会漏掉真正全局最优。

结点保存的“中点胜者”只是在经过该结点的竞争者中胜出，不保证它在这个中点是全树所有线的最优者。祖先还可能保存更优的线，这也是查询必须比较整条路径而不能只读叶子的原因。

先存 2x+3，再插入 -x+1 时根在 x=0 处交换，旧线下沉左子树；插入常数线 3 后进一步落入左区间的右孩子 — 中点留胜者，另一条线单侧下沉

例子与边界

不均匀坐标上的三次插入

取 $X=(-3,-1,0,2,5)$ ，依次插入

L_0(x)=2x+3,\qquad L_1(x)=-x+1,\qquad L_2(x)=3.

第一条存于根 $[0,5)$ 。第二条到来时，根中点下标 $h=2$ ，坐标 $x_2=0$ ； $L_1(0)=1<3=L_0(0)$ ，所以根改存 $L_1$ 。左端 $x=-3$ 时， $L_1=4$ 而 $L_0=-3$ ，旧线在左侧有优势，于是 $L_0$ 下沉到左孩子 $[0,2)$ 。

插入 $L_2$ 时，根中点仍由 $L_1$ 获胜，但在左端 $3<4$ ，所以 $L_2$ 进入左孩子。该结点中点为 $x_1=-1$ ， $L_0(-1)=1<3$ ；左端也由 $L_0$ 获胜，故 $L_2$ 被送到右孩子 $[1,2)$ 。这条常数线其实不在给定坐标上取得全局最小值，但保存它不会使答案变差。

查询 $x=-1$ 的路径上有 $L_1,L_0,L_2$ ，值分别为 $2,1,3$ ，返回 $(1,0)$ 。全部坐标上的答案为

$x$	$-3$	$-1$	$0$	$2$	$5$
最小值	$-3$	$1$	$1$	$-1$	$-4$
线编号	0	0	1	1	1

坐标间距是否均匀没有影响；只要求 $X$ 严格递增，左右子树对应真实坐标顺序。按下标中点二分还能保证每次区间严格缩小，避免连续坐标浮点中点反复等于端点的终止问题。

查询域、定义域与删除

这份实现只回答预先登记的坐标。若后来来了一个不在 $X$ 中的新坐标，需要重建坐标树，或从一开始采用带明确整数范围的另一种版本。不能把它临时插到排序数组里而仍沿用旧结点区间。

同斜率线和全相同线不会产生特殊交点问题，二元组比较能直接处理。插入的若是只在一段区间有效的线段，则先使用线段树的标准区间分解，只在覆盖结点内做线插入，通常增加一个对数因子；本页整条线插入的界不能原样沿用。删除也不由这一不变量自动支持，因为被压住的候选可能需要重新出现。

推论与应用

每次插入只沿一条根叶路径前进，查询也只访问一条路径，均为 $O(\log q+1)$ 次线值比较。坐标排序去重需 $O(q\log q)$ 预处理；查询可以通过二分找到下标，也可让调用方直接传下标。完整数组骨架占 $O(q)$ 空间；按需开结点时，每次插入遇到第一个空结点就停止，新增结点至多一个，所以 $L$ 次插入的占用为 $O(\min(L,q))$ 量级，外加坐标数组。

平方分段递推可以改写成 $S_j^2+\min_k\{(-2S_k)S_j+D_{t-1}[k]+S_k^2\}$ 。即使工作量带负数，前缀和查询和斜率插入都乱序，代数恒等式仍成立；登记所有前缀和坐标后，Li Chao 树可在每层 $O(n\log n)$ 次算术操作中求解。相比单调包络队列，它付出对数成本，换来无需两种单调顺序。

单元任务：给每次省略候选一份依据

完成两个相互独立的实验：先对 CACTUS 与 CATCUS 用完整表和 Hirschberg 重建单位替换模型的最优脚本，再对 ABCDA 与 BACDEA 用 Myers 重建最短插删脚本。逐条应用操作，确认得到目标串；前者费用 $2$ ，后者费用 $3$ ，并说明两者允许操作不同。

接着把负载 $(2,0,3,1,4,2,0,5,1,3,2,1)$ 分成四个非空连续批次，最小化批次总量平方和。实现朴素 DP、分治、SMAWK、单调直线队列和 Li Chao，统一最左切点。五种方法的每层值和切点都应相同，最终切点为 $4,6,9,12$ ，四段总量均为 $6$ ，总费用 $4\cdot6^2=144$ 。由四段总量之和为 $24$ ，平方和至少 $24^2/4=144$ ，得到独立最优性证书。

最后改用负载 $(-1,-2,-2,2)$ 、两段。真最优值为 $5$ ，切点为 $1$ ；分治在错误的单调性前提下会返回 $9$ ，Li Chao 仍返回 $5$ 。解释失败发生在哪个候选区间，以及哪项代数性质仍然有效。

下载完整题解、可运行 Python 核验脚本、逐表与逐事件结果。脚本只用标准库，包含空串、重复字符、零频率、相等斜率、平局和负负载反例。验收时分别报告求值次数、重建历史、数组与递归栈空间；不同方法统计的“表项查询”与“线比较”不能直接混作同一种计数。

参考资料

Chao Li, “The Li-Chao Tree: Algorithm Specification and Analysis”, arXiv:2603.07948v1, 2026-03-09 提交的预印本， §§3.1–3.4：作者预印本。单次交叉、插入分流不变量与查询正确性；本页具体实现采用离散半开下标区间。
UNSW COMP4128, Dynamic Programming II, 2021, “Convex Hull Trick”：官方讲义。直线下包络与平方 DP 转移的背景。

形式陈述 ​

不均匀坐标上的三次插入 ​

查询域、定义域与删除 ​

单元任务：给每次省略候选一份依据 ​

反向链接

形式陈述

不均匀坐标上的三次插入

查询域、定义域与删除

单元任务：给每次省略候选一份依据