haar_lib/algebra/
update_fold.rs

1//! Range Update Range ~~~
2pub use crate::algebra::{action::Action, first_last::Last, traits::*};
3use std::fmt::Debug;
4use std::marker::PhantomData;
5
6/// Range Update Range ~~~ 用の代数的構造
7///
8/// `convert`は時間計算量が$O(\log n)$なので、
9/// 遅延セグメント木に載せる場合は、更新・取得はともに$O(\log^2 n)$の計算量になることに注意。
10#[derive(Copy, Clone, Default, Debug, PartialEq, Eq)]
11pub struct UpdateFold<M: Monoid>(PhantomData<M>);
12
13impl<M> Action for UpdateFold<M>
14where
15    M: Monoid + Clone,
16{
17    type Output = M;
18    type Lazy = Last<M>;
19
20    fn convert(value: Self::Output, lazy: Self::Lazy, len: usize) -> Self::Output {
21        match lazy.0 {
22            Some(m) => m.times(len as u64),
23            _ => value,
24        }
25    }
26}

haar_lib/algebra/update_fold.rs

haar_lib/algebra/
update_fold.rs