The implementation of Segment Tree.

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;
}

#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Hash)]
pub struct SegTree<T> {
    vec: Vec<T>,
    size: usize,
}

impl<T: Monoid> SegTree<T> {
    pub fn new(size: usize) -> Self {
        let size = size.next_power_of_two();
        Self {
            vec: vec![T::ID; size * 2 - 1],
            size,
        }
    }

    pub fn clear(&mut self) {
        self.vec.fill(T::ID);
    }

    pub fn insert(&mut self, index: usize, value: T) {
        let mut index = index + self.size - 1;
        self.vec[index] = value;
        while 0 < index {
            index = (index - 1) / 2;
            self.vec[index] = self.vec[index * 2 + 1].op(self.vec[index * 2 + 2]);
        }
    }

    fn query_sub(&self, querying: std::ops::Range<usize>, index: usize, looking: std::ops::Range<usize>) -> T {
        if looking.end <= querying.start || querying.end <= looking.start {
            // looking does not contain querying
            T::ID
        } else if querying.start <= looking.start && looking.end <= querying.end {
            // looking completely contains querying
            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))
        }
    }

    pub fn query(&self, querying: std::ops::Range<usize>) -> T {
        self.query_sub(querying, 0, 0..self.size)
    }

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

    pub fn as_slice(&self) -> &[T] {
        &self.vec[self.size - 1..]
    }
}

wrapper_min.rs

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
struct Min(u32);

impl Monoid for Min {
    const ID: Self = Self(u32::MAX);
    fn op(self, other: Self) -> Self {
        Self(self.0.min(other.0))
    }
}