浅谈凸

ty_mxzhn · 2026-05-31 13:02:16 · 算法·理论

前言

非常非常浅谈。没有任何证明。

凸函数

如果从连续函数的角度定义，凸函数指的是导函数单调递增 / 递减的函数。

但是一般来讲是离散的，考虑整个序列的差分，其是单调递增的，就可以称作离散的凸函数。

凸包

计算几何中，如果一个封闭图形内任取两点，两点连成的直线完全在这个封闭图形内，那么这个封闭图形就是凸的。凸包是面积最小的包含若干个点的图形。

有一个形象的理解是拿出很多条直线，每条直线都往上去“切”这个凸包，就可以切出来整个凸包。

凸包可以拆成两部分，上凸壳和下凸壳，然后使用凸函数的维护技巧来维护。注意两侧的竖直线段无法表示成函数，需要特殊处理。

凸壳维护

凸壳可以支持在横坐标最右侧加点，只需要暴力把不满足下凸 / 上凸条件的点弹出即可。

可以用平衡树维护任意横坐标上加点的凸壳，直接暴力把不满足凸壳条件的点删了就行。其实这个平衡树可以只是一个 set。

斜率优化

一次函数 y=kx+b 如果过 (x_0,y_0) 一点，且 k 固定，解出 b=y_0-kx_0，所以如果我们选择一个斜率，然后平移直线直到第一次碰到关键点，就可以求形如给定 (x_0,y_0) 可能的关键点集合，求所有 y_0-kx_0 最值的问题。

所有可能被选入答案的点构成一个上 / 下凸壳。为了快速查询，可以二分。凸壳上的相邻三点的斜率是递增的，容易发现切点 p 满足相邻三个点 a,p,b 的斜率是 slope(a,p)\le k\le slope(p,b)，二分即可。

有时候不用二分，比如当斜率是单调的时可以使用一个单调队列来维护。加入新点时如果不是在最右侧，则需要用别的方法维护凸包保证复杂度。

这类题目例题很多，但是正赛对这种很死板的题目考的确实不多。尤其是斜率单调递增，横坐标也单调递增的平凡情况。

李超线段树

李超线段树的时间复杂度为操作单次 O(\log n)，注意和值域是无关的。虽然是动态开点，但是空间是 O(n) 的。

经典问题是全局插入直线，记点 x 的关键直线为 l_x，当且仅当若查询点为 x 时答案由 l_x 提供。

则我们要维护区间 [l,r] 的中点 m 的关键直线 l_m。当新加入一条直线 L_{new} 时，首先和当前直线比较，选择对于 m 来说更优的直线更新 l_m。

另一条直线从 [l,m] 和 [m,r] 中选择其可能比这条直线更优的区间，并递归。

查询时，不仅需要往下递归找到所有包含查询点的区间，而且还要同时考虑这些区间对查询点答案的贡献，不能只看最后一个。

本质：一个直线支配了剩下的直线，剩下的直线只能在一个更小的区间内产生影响，如此一个点只会被 \log n 个直线产生贡献。因为交点最多 n^2 个，显然也和值域无关。

拓展：第一，只需要满足被偏序的直线只被一个子区间接纳即可，不需要一定是直线。如果是一个相同的凸函数被平移了，一般也是可以的。

形式化的，三个点 a,b,c 满足 a<b<c，f(b)<g(b)，那么总有 x\in [b,c] 内 f(x)<g(x) 或者 x\in [a,b] 内 f(x)<g(x)。

给两个函数做差，那么满足 f(x)-g(x)=0 只有一个解的函数都可以。也就是交点唯一。

这个换句话说也像决策单调性，一个决策在一个前缀内比另一个决策优，后面就永远劣。

第二，区间插入线段也是可以的，先把线段拆成 O(\log V) 个区间，然后转化成这些区间内部整体插入线段即可。复杂度是 2log 的。

第二个拓展空间复杂度较高，如果查询的值固定可以优化。容易发现拆成 [l,m] 和 [m+1,r] 两个区间其实也没啥问题，所以可以写成普通线段树的形式。做到 O(n) 空间。

例题有很多就不放了。

wqs 二分

这个不是凸优化，是根据凸优化的结果求一个点值，但是还是放一下。

其实就是给一个物品赋一个附加权值 k，然后通过调用一个最优化的黑盒得到 f(x)-kx 的最值，最后通过查询若干次这个最值实现 f 的单点求值。

因为 f 是凸的，所以通过调整斜率会改变凸包上的切点，根据切点和要求值的位置的大小关系调整斜率。最后得到切线斜率之后直接计算即可。使用一个二分。

下面是一些细节。

比如现在你选一个物品要多花费 x 元，求花费的最少钱。

那么当你选完负花费的物品后，有一个问题，你要不要选 0 花费的物品。

这相当于，在下凸函数上，凸包上的多个点恰好贴合了一个直线。

如果你额外要求选择最小数目的物品，那么你想要的就是，选择数量 \le k 的最大数量，以及其对应花费的价值，以及对应的额外代价 x，然后再把答案加上 kx。

总之需要精细实现斜率刚好贴合的情况。

例题大家都知道就不放了。

决策单调性

决策单调性是字面意思，针对一个优化问题，随着条件的单调性，决策也具有单调性。需要注意的是这个优化问题一般不是凸的，但是和凸函数也有比较大的关系。

最经典的是四边形不等式带来的决策单调性，但我数学不好不会证，就跑路了。

先谈决策单调性的实现：常见的有两种，分治法和二分法。

分治法就是处理 [a,b] 这个条件区间，得到所有 y\in [a,b] 的 \min_x f_{y}(x)，已知可能的决策在 [l,r] 这个区间内，那么考虑中点 mid 的决策 p，然后递归到 [a,mid-1],[l,p] 和 [mid+1,b],[p,r] 两个子问题。

容易发现每一层划分出的决策点区间的总长最大是 m+n，设决策点总量有 m 个，复杂度为 O(m\log n+n)。缺点在于这个算法完全是离线的。

例题：CF868F。

当然如果你想的话，直接上个 CDQ 分治就可以 2log 解决在线问题！

二分法就是每次算第 i 个点的决策，那么首先这个决策要比 i-1 的决策大。然而这还不足以我们二分。所以二分法需要更强的条件。

例题：诗人小 G。

发现这题给的那个函数是凸的，联想上面李超树的结论，两个函数的平移至多只有一个交点。

所以一个决策只会在一段前缀内被另一个决策偏序，出了这个前缀他就可以偏序另一个决策。

记一个决策点的单调队列，并求出目前涉及的所有可能决策条件上，每个决策点被作为决策的区间，记为“控制范围”。我们每次要先做一次最优化，然后加入一个新决策点。

加入新决策点时和队尾比较，如果完全偏序了队尾则直接弹队尾，如果被队尾完全偏序则不继续加入决策，否则调整队尾的“控制范围”，并加入新决策点。

查询的时候查队头，如果队头的“控制范围”不包含 i 了就弹出队头。

那么这个更强的条件到底是什么呢？其实就是一个决策点永远在且仅在一个前缀内被另一个决策点偏序。换句话说，这个矩阵是一个完全单调矩阵。单调矩阵是每行最小值位置非严格单增的矩阵。而完全单调矩阵是任意一个子矩阵都满足这个条件的矩阵。子矩阵是任取一些行或列交出来的矩阵。而 n=2 的矩阵显然取到了最严格的限制，所以这两个条件是等价的。

满足四边形不等式的矩阵叫蒙日矩阵，蒙日矩阵一定有完全单调性。

(\min,+) 卷积

定义其实就是 f_{k}=\min_{i+j=k}g_i+h_j。