haar_lib/algebra/
action.rs

1//! 遅延セグメント木などに載せる構造
2pub use crate::algebra::traits::*;
3
4/// 遅延セグメント木などに載せる構造
5pub trait Action {
6    /// 範囲取得の型
7    type Output: Monoid;
8    /// 範囲更新の型
9    type Lazy: Monoid;
10
11    /// 範囲取得のモノイドの単位元を返す。
12    fn fold_id() -> Self::Output {
13        Self::Output::id()
14    }
15    /// 範囲取得のモノイドの二項演算を適用させる。
16    fn fold(a: Self::Output, b: Self::Output) -> Self::Output {
17        a.op(b)
18    }
19    /// 範囲更新のモノイドの単位元を返す。
20    fn update_id() -> Self::Lazy {
21        Self::Lazy::id()
22    }
23    /// 範囲更新のモノイドの二項演算を適用させる。
24    fn update(cur: Self::Lazy, next: Self::Lazy) -> Self::Lazy {
25        cur.op(next)
26    }
27    /// 範囲更新を範囲取得に反映させる。
28    fn convert(value: Self::Output, lazy: Self::Lazy, len: usize) -> Self::Output;
29}
haar_lib/algebra/action.rs

haar_lib/algebra/
action.rs
