编程面试：如何用 Li Chao Tree 支持动态直线区间最小值？
题干与适用场景
系统在线接收直线 y = m x + b，支持任意顺序插入；查询给定整数 x 上所有直线的最小值。查询点不单调，斜率也不单调。扩展问题可能要求直线只在区间 [l, r] 有效，或把查询改为最大值。
这道题适合考察动态规划优化、分治不变量和线段树实现。强回答要先说明值域是否离散且有界，再解释每个节点只保留一条“在某个位置胜出”的候选直线，并证明被淘汰的直线不会在该节点区间重新胜出。
面试官考察点
- 能否从每次扫描全部直线的
O(n)查询推导瓶颈。 - 是否理解中点比较、交换和递归方向构成的 Li Chao 不变量。
- 能否处理任意斜率、重复直线、负坐标和极值溢出。
- 是否区分离散整数值域、连续域和区间直线三种实现边界。
- 是否给出
O(log C)单次插入/查询和O(log C)线段插入复杂度。 - 能否说明单调斜率与单调查询时，普通 Convex Hull Trick 可能更简单。
回答前需要澄清的问题
- 查询
x是整数还是实数？值域是固定[L, R]还是动态扩展？这决定递归深度和是否需要坐标压缩。 - 要最小值还是最大值？是否允许空集合？空集合的哨兵值要避免与真实答案冲突。
- 斜率、截距和答案的最大绝对值是多少？需要多宽的整数或饱和乘法？
- 直线是否只在
[l, r]生效？区间插入会把一条线分发到多个树节点。 - 斜率插入或查询是否单调？若单调，单调队列式 CHT 可能比 Li Chao 更省常数。
30 秒回答框架
我先把整数查询域 [L,R] 建成线段树，每个节点保存一条当前候选直线。插入新线时比较左右端点和中点；若新线在中点更优，就和节点线交换。交换后，旧线只可能在左半或右半继续胜出，因此根据端点比较把它递归到一侧。查询沿根到叶子路径取所有节点直线值的最小值。值域长度为 C 时插入和查询都是 O(log C)，区间直线插入为 O(log^2 C)；需要最大值时把比较方向反过来。
分步骤深入解答
1. 朴素方案与瓶颈
维护一个直线列表，每次查询计算所有 m x + b 的最小值，时间是 O(numberoflines)。若这是动态规划中的转移，插入和查询交错且顺序任意，排序斜率或查询点不能依赖，因此需要把比较工作分摊到值域区间。
2. 节点不变量
节点代表一个闭区间 [lo, hi]，保存直线 cur。不变量是：在该区间内，所有尚未递归到子节点的直线中，cur 在至少一个候选位置不劣；其余直线若仍可能成为最优，只会被送到左子区间或右子区间。叶子节点只需保存在单点上最优的直线。
3. 中点交换和递归方向
设新线为 nw，节点线为 cur，中点为 mid。若新线在 mid 的值小于节点线，交换两线，使节点保留中点更优者。交换后比较 nw(lo) 与 cur(lo)：若旧线在左端更优，它可能在左侧重新胜出，递归左子；否则比较右端并递归右子。直线差值是一次函数，两个交点之间不可能来回交替，所以只需递归一侧。
add(node, lo, hi, nw):
mid = (lo + hi) // 2
left = nw(lo) < cur(lo)
middle = nw(mid) < cur(mid)
if middle: swap(nw, cur)
if lo == hi: return
if left != middle: add(leftChild, lo, mid, nw)
else: add(rightChild, mid + 1, hi, nw)实现中要使用安全的中点公式，并在 m * x + b 可能超过 64 位时使用更宽整数、检查或饱和策略。
4. 查询路径
查询单点 x 时，从根递归到包含 x 的叶子，同时计算每个节点保存直线在 x 的值并取最小值。树上其他区间不包含该点，不需要访问。若使用动态节点，只为实际插入经过的区间分配内存；空节点返回正无穷哨兵。
5. 区间直线插入
若直线只在 [ql, qr] 生效，可把它按普通线段树区间分解，完整覆盖的节点直接执行一次 Li Chao 插入，部分覆盖则继续递归。区间分解访问 O(log C) 个节点，每个节点插入 O(log C)，总复杂度是 O(log^2 C)，查询仍为 O(log C)。
6. 离散坐标与连续查询
若只查询已知的离散 x 集合，先排序去重并用索引作为叶子域，避免为巨大空值域建树。若查询是实数，必须给出精度和终止条件；普通 Li Chao 的整数递归证明不能直接套用无限连续域，通常要限定区间并设定浮点比较误差。
7. 与 Convex Hull Trick 的取舍和测试
斜率单调、查询点也单调时，deque 维护的 CHT 常数更小；斜率任意、查询任意时 Li Chao 更稳健，但节点和递归常数更大。测试要覆盖空集合、单点域、重复斜率、相同直线、负坐标、交点恰在中点、直线只覆盖一个端点、极大乘积和最大值查询，并与逐条枚举结果比较。
高质量示范回答
我会先确认查询域是固定整数区间，还是需要坐标压缩。对 [L,R] 建 Li Chao Tree，每个节点存一条当前候选线。插入时比较端点和中点；中点更优的线留在节点，另一条线依据两条直线的相对顺序只递归到左或右子区间。因为两条直线的差是一次函数，旧线不可能在两个不相邻方向重新胜出。单点查询沿一条根叶路径取最小值，插入和查询都是 O(log C)。若斜率与查询都单调，我会改用 CHT；若线段有生效区间，则先做线段树分解，复杂度变为 O(log^2 C)。
常见错误
- 只比较中点不递归 → 另一条线可能在端点胜出 → 结合端点与中点决定唯一递归方向。
- 假设斜率必须单调 → 任意顺序时结果错误 → 用 Li Chao 的区间不变量，或明确改用适用的 CHT 前提。
- 用
m * x + b的 64 位乘法无检查 → 极值溢出改变比较顺序 → 使用更宽类型或显式溢出策略。 - 动态域无限扩展 → 递归没有终点 → 先限定整数域、离散化坐标或设定浮点精度。
- 区间插入直接复制到每个叶子 → 复杂度退化 → 用线段树区间分解后在完整覆盖节点插入。
- 空节点返回零 → 最小值被错误压低 → 使用与答案范围隔离的正无穷哨兵。
追问及应对
如果要求最大值怎么办？
把比较方向全部反转，或把每条直线的 m 与 b 同时取反后求最小值再取相反数。要保持空集合和溢出语义一致，不能只改最终返回值。
值域达到 10 的 18 次方，仍能开数组树吗？
不能预分配所有节点。使用隐式动态树，只在插入访问的路径上创建节点；递归深度约为值域位数。若实际查询坐标有限，坐标压缩通常更省内存。
两条直线在中点相等，如何避免错误分支？
固定一个平局规则，例如优先保留旧线或按斜率排序。分支判断使用严格不等式并在端点比较中保持同一规则，确保相同直线不会无限递归。
如何证明只递归一边？
两条直线之差仍是一次函数，最多只有一个交点。交换后若旧线在中点更差，它若能在区间内胜出，只能位于一个端点方向；端点与中点的符号变化唯一确定左或右。
什么时候 CHT 更合适？
当直线斜率按单调顺序加入、查询点也单调时，凸包队列可以摊销 O(1) 查询或 O(log n) 查询，代码和内存更小。斜率或查询乱序、需要区间直线时，Li Chao 的通用性更有价值。