Slope Trick

标签：Slope begin end 函数 转折点 Trick

原理

若一个函数满足：

1. 连续
2. 分段线性
3. 凸性
   则可以使用 Slope Trick 来快速维护。

我们发现我们可以仅通过记录转折点，转折点处斜率变化，以及一侧的直线即可维护出整个函数。具体而言每一个转折点出现，我们就认为该函数在该点斜率变化了 1.
举个例子，对于如下函数：

\[\begin{equation} y(x)=\left\{ \begin{aligned} -x & \quad x<0\\ 0 & \quad 0\leq x \leq 2\\ 2x + 3 & \quad x>2\\ \end{aligned} \right. \end{equation} \]

标签：Slope,begin,end,函数,转折点,Trick
From： https://www.cnblogs.com/zym417/p/17155395.html