The implementation of Lazy Eval Segmentation Tree.

lazy_seg_tree.rs

/// Monoid must satisfy:
/// ```rs
/// fn test<M: Monoid>(m: M, n: M, l: M) {
///   assert_eq!(m.op(M::ID), m);
///   assert_eq!(M::ID.op(m), m);
///   assert_eq!(m.op(n.op(l)), m.op(n).op(l));
/// }
/// ```
pub trait Monoid: Copy + Eq {
    const ID: Self;
    fn op(self, other: Self) -> Self;
}

/// ActMonoid must satisfy:
/// ```rs
/// fn test<M: ActMonoid>(m: M, n: M, a: M::Act, b: M::Act) {
///   assert_eq!(m.act(a.op(b)), m.act(a).op(m.act(b)));
///   assert_eq!(m.act(a.op(b)), m.act(a).act(b));
/// }
/// ```
pub trait ActMonoid: Monoid {
    type Act: Monoid;
    fn act(self, other: Self::Act) -> Self;
}

/// The lazy-eval segment tree.
#[derive(Debug)]
pub struct LazySegTree<T: ActMonoid> {
    vec: Vec<T>,
    lazy: Vec<T::Act>,
    size: usize,
}

impl<T: ActMonoid> LazySegTree<T> {
    /// Creates a lazy-eval segment tree which has length of `size`.
    pub fn new(size: usize) -> Self {
        let size = size.next_power_of_two();
        Self {
            vec: vec![T::ID; size * 2 - 1],
            lazy: vec![T::Act::ID; size * 2 - 1],
            size,
        }
    }
    
    pub fn clear(&mut self) {
        self.vec.fill(T::ID);
        self.lazy.fill(T::Act::ID);
    }

    fn eval(&mut self, on: usize) {
        let new_val = self.lazy[on];
        if new_val == T::Act::ID {
            return;
        }
        if on < self.size - 1 {
            self.lazy[on * 2 + 1] = self.lazy[on * 2 + 1].op(new_val);
            self.lazy[on * 2 + 2] = self.lazy[on * 2 + 2].op(new_val);
        }
        self.vec[on] = self.vec[on].act(new_val);
        self.lazy[on] = T::Act::ID;
    }

    fn update_sub(
        &mut self,
        value: T::Act,
        index: usize,
        setting: std::ops::Range<usize>,
        looking: std::ops::Range<usize>,
    ) {
        self.eval(index);
        if setting.start <= looking.start && looking.end <= setting.end {
            self.lazy[index] = self.lazy[index].op(value);
            self.eval(index);
        } else if setting.start < looking.end && looking.start < setting.end {
            let mid = looking.start + (looking.end - looking.start) / 2;
            self.update_sub(value, index * 2 + 1, setting.clone(), looking.start..mid);
            self.update_sub(value, index * 2 + 2, setting, mid..looking.end);
            self.vec[index] = self.vec[index * 2 + 1].op(self.vec[index * 2 + 2]);
        }
    }

    /// Updates the values in the range `setting` by `value`.
    pub fn update(&mut self, value: T::Act, setting: std::ops::Range<usize>) {
        self.update_sub(value, 0, setting, 0..self.size);
    }

    fn query_sub(&mut self, querying: std::ops::Range<usize>, index: usize, looking: std::ops::Range<usize>) -> T {
        self.eval(index);
        if looking.end <= querying.start || querying.end <= looking.start {
            // querying does not contain looking
            T::ID
        } else if querying.start <= looking.start && looking.end <= querying.end {
            // querying completely contains looking
            self.vec[index]
        } else {
            let mid = looking.start + (looking.end - looking.start) / 2;
            self.query_sub(querying.clone(), index * 2 + 1, looking.start..mid)
                .op(self.query_sub(querying, index * 2 + 2, mid..looking.end))
        }
    }

    /// Queries the value of the range `querying`.
    pub fn query(&mut self, querying: std::ops::Range<usize>) -> T {
        self.query_sub(querying, 0, 0..self.size)
    }

    pub fn get(&mut self, index: usize) -> T {
        self.query(index..index + 1)
    }
}

max.rs

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Max(u32);

impl Monoid for Max {
    const ID: Self = Self(0);
    fn op(self, other: Self) -> Self {
        Self(self.0.max(other.0))
    }
}

impl ActMonoid for Max {
    type Act = Self;
    fn act(self, other: Self::Act) -> Self {
        Self(self.0.max(other.0))
    }
}