Convex-hull trick

释义 Definition

“凸包技巧”（常写作 Convex Hull Trick, CHT）：一种算法优化方法，用来在一组一次函数（直线）中高效地进行“加入直线”和“查询最小值/最大值”。常用于把某些动态规划（DP）从 \(O(n^2)\) 优化到 \(O(n \log n)\) 或 \(O(n)\)。

例句 Examples

We used the convex-hull trick to speed up the DP transitions.
我们用凸包技巧来加速动态规划的转移。

In problems where each state adds a line and later queries the best value, the convex-hull trick can reduce the time complexity dramatically.
在那些每个状态都会加入一条直线、之后又要查询最优值的问题中，凸包技巧可以显著降低时间复杂度。

发音 Pronunciation (IPA)

/ˈkɑn.vɛks hʌl trɪk/

词源 Etymology

该术语由三部分构成：convex（凸的）+ hull（外壳；几何中的“凸包”）+ trick（技巧/小窍门）。名字源于几何直观：把“直线集合”在某种对偶/几何视角下与“凸包边界”联系起来，通过维护类似“凸包”的结构来快速找到最优直线，因此得名“凸包技巧”。

相关词 Related Words

• Convex
• Hull
• Convex Hull
• Dynamic Programming
• Line Container
• Li Chao Tree
• Divide And Conquer Optimization
• Monotone Queue
• Upper Envelope

文学与著作中的用例 Literary Works

• Competitive Programming 3（Steven Halim 等）：在 DP 优化章节中介绍 CHT 作为经典技巧之一。
• CP-Algorithms（在线算法参考资料，常被整理成书/讲义版本）：在“Convex Hull Trick”条目中系统讲解实现与适用条件。
• *KACTL (KTH Algorithm Competition Template Library)*：以“LineContainer/Convex Hull Trick”形式给出可复用实现，并在竞赛题解中频繁出现。