Slope Trick 学习笔记

slope trick 貌似没有正式引进，所以以原文记下

slope trick 的背景知识

“slope trick” 实际上就是描述函数的一种方式，能使用 slope trick 表示的函数(slope-trick-able)具有以下特性：

• 连续
• 可分为若干个线性函数，每个线性函数有着固定的斜率
• 是一个凸函数/凹函数（单调递增或单调递减）

这里举一个非常简单的例子，$f(x) = \lvert x \rvert$ 就是一个可以使用 slope trick 的函数：

它可以被分为左右两端线性函数 $f_1(x) = -x$ 和 $f_2(x) = x$，容易看出它满足上述的所有性质。

怎么使用 slope trick

定义 “changing point” 为函数斜率发生变化的点的横坐标，如 $f(x)$ 的 changing point 就是 $0$：在它左边的 $f_1(x)$ 的斜率为 $-1$ 而右边的 $f_2(x)$ 的斜率则是 $1$。

我们考虑使用只使用 changing point $k$ 来表示函数：定义一个 multiset (可重集) $\mathbf{S}$，changing point 变化时就在 $\mathbf{S}$ 中插入 changing point 它的大小 $\Delta k$ 次，再加上最后一段的直线表达式。

可能有点拗口，还是以绝对值函数为例子：我们可以得到 $[f_2 = x, \mathbf{S} = \{0, 0\}]$。

如我们所见，最后一段函数 $f_2(x)$ 的表达式加上 changing point($0$) $1 - (-1) = 2$ 次。

注意到这种表达方式通常要求我们的 slope-trick-able 函数的斜率比较小。

怎么通过这个集合复原它呢？注意到 $f(x)$ 函数可以这样分出来：$(-\infty, 0), [0, \infty)$，最后一段的表达式 $f_2 = x$，倒数第二段 $f_2 = -x$ 因为 $f_2 = (1 - 1 - 1) x$。

slope trick 有着极为优美的性质：mergable。

如果 $\theta_1(x)$ 和 $\theta_2(x)$ 都是 slope-trick-able 的函数并且他们的凸性或者凹性相同，那么他们是可以非常简单地进行合并的：

合并后的函数 $\theta_{3}(x)$ 满足$\mathbf{S_{\theta_3}} = \mathbf{S_{\theta_1}} \cup \mathbf{S_{\theta_2}}$，合并过程类似扫描线？每次我们压入两个新的 slope-trick-able 函数，只需要简单地联立起所有的 changing point 即可。

可以引申出不少 slope trick 常见的非常好用的性质：

• 相加：把 $\theta(x), k$ 直接相加，合并 $\mathbf{S}$
• 取前缀/后缀 $\min$：由于满足凸函数性质或者凹函数性质，直接去掉 $k \lt 0 / k \gt 0$ 的部分就可
• 平移/翻转：维护 $\theta(x_0) 和 k_0$ 的变化之后斜率变化点在全局打平移/翻转标记
• 似乎可以查询 max/min，还没看懂

参考：

• [Tutorial] Slope Trick - zscoder
• Slope trick explained - Kuroni
• [Tutorial] Intuition on Slope Trick
• [学习笔记] Slope Trick - CCComfy
• Slope Trick 总结 - rui_er