Struct UpdateFold

pub struct UpdateFold<M: Monoid>(/* private fields */);

Range Update Range ~~~ 用の代数的構造

convertは時間計算量が$O(\log n)$なので、 遅延セグメント木に載せる場合は、更新・取得はともに$O(\log^2 n)$の計算量になることに注意。

Trait Implementations

impl<M> Action for UpdateFold<M>

where M: Monoid + Clone,

type Output = M

範囲取得の型

type Lazy = Last<M>

範囲更新の型

fn convert(value: Self::Output, lazy: Self::Lazy, len: usize) -> Self::Output

範囲更新を範囲取得に反映させる。

fn fold_id() -> Self::Output

範囲取得のモノイドの単位元を返す。

fn fold(a: Self::Output, b: Self::Output) -> Self::Output

範囲取得のモノイドの二項演算を適用させる。

fn update_id() -> Self::Lazy

範囲更新のモノイドの単位元を返す。

fn update(cur: Self::Lazy, next: Self::Lazy) -> Self::Lazy

範囲更新のモノイドの二項演算を適用させる。

impl<M: Clone + Monoid> Clone for UpdateFold<M>

fn clone(&self) -> UpdateFold<M>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<M: Debug + Monoid> Debug for UpdateFold<M>

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

Formats the value using the given formatter.

impl<M: Default + Monoid> Default for UpdateFold<M>

fn default() -> UpdateFold<M>

Returns the “default value” for a type.

impl<M: PartialEq + Monoid> PartialEq for UpdateFold<M>

fn eq(&self, other: &UpdateFold<M>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<M: Copy + Monoid> Copy for UpdateFold<M>

impl<M: Eq + Monoid> Eq for UpdateFold<M>

impl<M: Monoid> StructuralPartialEq for UpdateFold<M>