Trait libpuri::LazyAct

pub trait LazyAct<M: Monoid>: Monoid {
    pub fn act(&self, m: &M) -> M;
}

Trait for the relationship between two monoids in the LazySegTree

A lazy segment tree requires two monoids M and A, which represent the property of interval and the lazy action on the range, respectively.

M only need to be a monoid while A need to satisfy both monoid and lazy action properties. By implementing LazyAct you are confirming that the action of A on M satisfies following conditions:

// Composite of two maps is the product of two corresponding monoids.
f(g(m)) == (f * g)(m)
 
// The identity of `A` should map m from `M` to itself.
id(m) == m
 
// The corresponding map of an element of `A` should be homomorphic.
f(m * n) == f(m) * f(n)

Here the first two conditions are for a monoid action and the third is only for the lazy segment tree.

Required methods

pub fn act(&self, m: &M) -> M

An action of a lazy monoid to an interval monoid.

Loading content...

Implementors

Loading content...