slope_trick
クラス · slope trick
template <class T>
struct slope_trick;
概要
slope trick
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
定数 $0$ の凸関数を構築する | $O(1)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
min_x |
最小値を取る $x$ の 1 つを返す | $O(1)$ |
min_value |
関数の最小値を返す | $O(1)$ |
add_const |
$f(x) \gets f(x) + a$ | $O(1)$ |
add_x_minus_a |
$f(x) \gets f(x) + \max(0, x - a)$ | $O(\log n)$ |
add_a_minus_x |
$f(x) \gets f(x) + \max(0, a - x)$ | $O(\log n)$ |
add_abs |
$f(x) \gets f(x) + |x - a| = f(x) + \max(0, x - a) + \max(0, a - x)$ | $O(\log n)$ |
clear_right |
$f(x) \gets \min_{y \le x} f(y)$ | $O(1)$ |
clear_left |
$f(x) \gets \min_{y \ge x} f(y)$ | $O(1)$ |