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,还没看懂
参考: