Struct nekolib::math::SlopeFunction

pub struct SlopeFunction<I: Ord> { /* private fields */ }

区分線形凸関数。

整数の多重集合 $L$, $R$ に対して、次の形で表せる関数を管理する： $$ f(x) = c + \sum_{l\in L} (l-x)_+ + \sum_{r\in R} (x-r)_+. $$ ここで、$(a-x)_+ = \max\{0, a-x\}$、$(x-a)_+ = \max\{0, x-a\}$ とする。 たとえば、$|x-a| = (a-x)_+ + (x-a)_+$ と書ける。

Idea

todo!()

Complexity

演算	時間計算量
new	$O(1)$
add_const	$O(1)$
add_left, add_right, add_abs	$O(\log(|L|) + \log(|R|))$
min_left, min_right	amortized $O(1)$
shift, window	$O(1)$
min, argmin	$O(1)$

Examples

use std::ops::Bound::{Included, Unbounded};

use nekolib::math::SlopeFunction;

let mut sf = SlopeFunction::new();
sf.add_left(-1);
sf.add_left(3);
sf.add_right(2);
sf.add_const(-10);
// f(x) = 0.max(-1-x) + 0.max(3-x) + 0.max(x-2) - 10
//   x  | -5 -4 -3 -2 -1  0  1  2  3  4  5
// f(x) |  2  0 -2 -4 -6 -7 -8 -9 -9 -8 -7
assert_eq!(sf.min(), -9);
assert_eq!(sf.argmin(), (Included(2), Included(3)));

Notes

$(a_1, a_2, \dots, a_n)$ の中央値を $a_{\text{med}}$ とすると、 $\sum_{i=1}^n |x-a_i|$ は $x = a_{\text{med}}$ のとき最小となる。 このことから、値の追加と中央値を求めるクエリを処理できる。

use std::ops::Bound::{Included, Excluded, Unbounded};

use nekolib::math::SlopeFunction;

#[derive(Clone, Default)]
struct IncrementalMedian(SlopeFunction<i32>);

impl IncrementalMedian {
    fn new() -> Self { Self::default() }
    fn insert(&mut self, a: i32) { self.0.add_abs(a); }
    fn median(&self) -> Option<i32> {
        match self.0.argmin().0 {
            Included(x) => Some(x),
            Excluded(_) => unreachable!(),
            Unbounded => None,
        }
    }
}

let mut im = IncrementalMedian::new();
assert_eq!(im.median(), None); // {{}}
im.insert(2);
assert_eq!(im.median(), Some(2)); // {{2}}
im.insert(3);
assert_eq!(im.median(), Some(2)); // {{2, 3}}
im.insert(1);
assert_eq!(im.median(), Some(2)); // {{1, 2, 3}}
im.insert(1);
assert_eq!(im.median(), Some(1)); // {{1, 1, 2, 3}}

References

• https://maspypy.com/slope-trick-1-%E8%A7%A3%E8%AA%AC%E7%B7%A8

Implementations

impl<I: SlopeTrickInt> SlopeFunction<I>

pub fn new() -> Self

$f(x) = 0$ で初期化する。

Examples

use std::ops::Bound::Unbounded;

use nekolib::math::SlopeFunction;

let sf = SlopeFunction::<i32>::new();
assert_eq!(sf.min(), 0);
assert_eq!(sf.argmin(), (Unbounded, Unbounded));

pub fn add_const(&mut self, c: I)

$f(x) \xleftarrow{+} c$ で更新する。

Examples

use nekolib::math::SlopeFunction;

let mut sf = SlopeFunction::new();
assert_eq!(sf.min(), 0);
sf.add_const(3);
assert_eq!(sf.min(), 3);
sf.add_const(-1);
assert_eq!(sf.min(), 2);

pub fn add_left(&mut self, l: I)

$f(x) \xleftarrow{+} (l-x)_+$ で更新する。

Examples

use std::ops::Bound::{Included, Unbounded};

use nekolib::math::SlopeFunction;

let mut sf = SlopeFunction::new();
sf.add_left(4);
assert_eq!(sf.argmin(), (Included(4), Unbounded));

pub fn add_right(&mut self, r: I)

$f(x) \xleftarrow{+} (x-r)_+$ で更新する。

Examples

use std::ops::Bound::{Included, Unbounded};

use nekolib::math::SlopeFunction;

let mut sf = SlopeFunction::new();
sf.add_right(4);
assert_eq!(sf.argmin(), (Unbounded, Included(4)));

pub fn add_abs(&mut self, a: I)

$f(x) \xleftarrow{+} |x-a|$ で更新する。

Examples

use std::ops::Bound::Included;

use nekolib::math::SlopeFunction;

let mut sf = SlopeFunction::new();
sf.add_abs(4);
assert_eq!(sf.argmin(), (Included(4), Included(4)));

pub fn min_left(&mut self)

$g(x) = \min_{y\le x} f(y)$ として、$f\gets g$ で更新する。

Examples

use std::ops::Bound::{Included, Unbounded};

use nekolib::math::SlopeFunction;

let mut sf = SlopeFunction::new();
sf.add_abs(4);
assert_eq!(sf.argmin(), (Included(4), Included(4)));
sf.min_left();
assert_eq!(sf.argmin(), (Included(4), Unbounded));

pub fn min_right(&mut self)

$g(x) = \min_{y\ge x} f(y)$ として、$f\gets g$ で更新する。

Examples

use std::ops::Bound::{Included, Unbounded};

use nekolib::math::SlopeFunction;

let mut sf = SlopeFunction::new();
sf.add_abs(4);
assert_eq!(sf.argmin(), (Included(4), Included(4)));
sf.min_right();
assert_eq!(sf.argmin(), (Unbounded, Included(4)));

pub fn shift(&mut self, s: I)

$g(x) = f(x-a)$ として、$f\gets g$ で更新する。

Examples

use std::ops::Bound::Included;

use nekolib::math::SlopeFunction;

let mut sf = SlopeFunction::new();
sf.add_abs(4);
assert_eq!(sf.argmin(), (Included(4), Included(4)));
sf.shift(2);
assert_eq!(sf.argmin(), (Included(6), Included(6)));

pub fn window(&mut self, window: RangeInclusive<I>)

$[a, b]$ に対して $g(x) = \min_{y\in[x-b, x-a]} f(y)$ として、$f\gets g$ で更新する。

Examples

use std::ops::Bound::Included;

use nekolib::math::SlopeFunction;

let mut sf = SlopeFunction::new();
sf.add_abs(4);
assert_eq!(sf.argmin(), (Included(4), Included(4)));
sf.window(-1..=2);
assert_eq!(sf.argmin(), (Included(3), Included(6)));

pub fn min(&self) -> I

$\min_{x\in\mathbb{R}} f(x)$ を返す。

Examples

use nekolib::math::SlopeFunction;

let mut sf = SlopeFunction::new();
sf.add_abs(4);
sf.add_const(1);
assert_eq!(sf.min(), 1);

pub fn argmin(&self) -> (Bound<I>, Bound<I>)

$\argmin_{x\in\mathbb{R}} f(x)$ を返す。

Examples

use std::ops::Bound::Included;
use nekolib::math::SlopeFunction;

let mut sf = SlopeFunction::new();
sf.add_abs(4);
sf.add_const(1);
assert_eq!(sf.argmin(), (Included(4), Included(4)));

Trait Implementations

impl<I: Clone + Ord> Clone for SlopeFunction<I>

fn clone(&self) -> SlopeFunction<I>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<I: Debug + Ord> Debug for SlopeFunction<I>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<I: Default + Ord> Default for SlopeFunction<I>

fn default() -> SlopeFunction<I>

Returns the “default value” for a type.