凸包技巧（Convex Hull Trick，CHT）：一种常用于优化动态规划的算法技巧，把转移式改写成若干条直线（线性函数）的最小值/最大值查询问题，通过维护这些直线的“下凸包/上凸包”（更准确说是下/上包络线），将朴素的 \(O(n^2)\) 优化到常见的 \(O(n \log n)\) 或在特定单调条件下到 \(O(n)\)。
（也常见于斜率优化 DP；此外还有 Li Chao Tree 等实现变体。）
/ˈkɒn.vɛks hʌl trɪk/（UK）, /ˈkɑːn.vɛks hʌl trɪk/（US）
I used the convex hull trick to speed up my DP.
我用凸包技巧把我的动态规划加速了。
When the slopes are monotonic, the convex hull trick can answer minimum queries efficiently by maintaining the lower envelope of lines.
当斜率满足单调性时，凸包技巧可以通过维护直线的下包络线来高效回答最小值查询。
该术语由两部分组成：convex hull（凸包）来自计算几何，指包含一组点的最小凸多边形；在 CHT 中，思想类比为维护一组直线在某些查询点上的最优“外壳/包络”。trick（技巧）在程序竞赛语境里常指一种“常用优化套路/手法”，并非数学上的“技巧性小招”，而是一类系统性的优化方法。
Select Language