haar_lib/algebra/act/
update_fold.rs

1//! Range Update Range ~~~
2pub use crate::algebra::{act::Act, first_last::Last, traits::*};
3
4/// Range Update Range ~~~ 用のモノイド作用
5///
6/// `act_n`は時間計算量が$O(\log n)$なので、
7/// 遅延セグメント木に載せる場合は、更新・取得はともに$O(\log^2 n)$の計算量になることに注意。
8#[derive(Copy, Clone, Default, Debug, PartialEq, Eq, Hash)]
9pub struct UpdateFold<T>(pub Last<T>);
10
11impl<T, M> Act<M> for UpdateFold<T>
12where
13    M: Monoid<Element = T>,
14    M::Element: Clone,
15{
16    type Monoid = Last<T>;
17    type Element = Option<T>;
18
19    fn monoid(&self) -> &Self::Monoid {
20        &self.0
21    }
22    fn act(&self, m: &M, val: <M>::Element, a: Self::Element, len: usize) -> <M>::Element {
23        match a {
24            Some(a) => m.times(a, len as u64),
25            _ => val,
26        }
27    }
28}