haar_lib/algebra/act/
mod.rs

1//! 遅延セグメント木などに載せる構造
2pub mod add_min_count;
3pub mod add_sum;
4pub mod affine_sum;
5pub mod chmax_max;
6pub mod chmin_min;
7pub mod mul_prod;
8pub mod mul_sum;
9pub mod update_fold;
10pub mod update_sum;
11
12pub use crate::algebra::traits::*;
13
14/// モノイド作用
15pub trait Act<M: Monoid> {
16    /// 作用させるモノイド
17    type Monoid: Monoid<Element = Self::Element>;
18    /// モノイドの元
19    type Element;
20
21    /// 作用させるモノイドへの参照を返す。
22    fn monoid(&self) -> &Self::Monoid;
23
24    /// $val$を`n`個の値からなる列をモノイド$(\circ, e)$で畳み込んだ値であるとしたとき、
25    /// 列の各値に$a$を作用させて畳み込んだ値を求める。
26    ///
27    /// 畳み込んだ値が同一になるような、長さ`n`のいかなる列に対しても、$a$を作用させて畳み込んだ値はすべて同一でなければならない。
28    fn act(&self, m: &M, val: M::Element, a: Self::Element, n: usize) -> M::Element;
29
30    /// `self.act(m, val, a, 1)`
31    fn act_one(&self, m: &M, val: M::Element, a: Self::Element) -> M::Element {
32        self.act(m, val, a, 1)
33    }
34
35    /// 二項演算
36    fn op(&self, a: Self::Element, b: Self::Element) -> Self::Element {
37        self.monoid().op(a, b)
38    }
39    /// 単位元
40    fn id(&self) -> Self::Element {
41        self.monoid().id()
42    }
43}
haar_lib/algebra/act/mod.rs

haar_lib/algebra/act/
mod.rs
