Querying group sum of range by event sourcing method with Rust.

range_q.rs

/// Group must satisfy:
/// ```rs
/// fn test<G: Group>(m: G, n: G, l: G) {
///     assert_eq!(m.op(&G::id()), m);
///     assert_eq!(G::id().op(&m), m);
///     assert_eq!(m.op(&n.op(&l)), m.op(&n).op(&l));
///     assert_eq!(m.op(&m.inv()), G::id());
///     assert_eq!(m.inv().op(&m), G::id());
/// }
/// ```
pub trait Group {
    fn id() -> Self;
    fn op(&self, other: &Self) -> Self;
    fn inv(&self) -> Self;
}

#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct RangeQ<T> {
    cum: Vec<T>,
}

impl<T> RangeQ<T> {
    pub const fn new() -> Self {
        Self { cum: vec![] }
    }

    pub fn from<I>(values: I) -> Self
    where
        I: IntoIterator<Item = T>,
        T: Group + Clone,
    {
        Self {
            cum: values
                .into_iter()
                .scan(T::id(), |state, item| {
                    *state = state.op(&item);
                    Some(state.clone())
                })
                .collect(),
        }
    }

    pub fn len(&self) -> usize {
        self.cum.len()
    }

    pub fn is_empty(&self) -> bool {
        self.cum.is_empty()
    }

    /// Sums up at index from `0` (inclusive) to `end` (exclusive).
    pub fn sum_from_start_to(&self, end: usize) -> T
    where
        T: Clone + Group,
    {
        if end == 0 {
            T::id()
        } else {
            self.cum
                .get(end - 1)
                .or_else(|| self.cum.last())
                .cloned()
                .unwrap_or_else(T::id)
        }
    }

    pub fn sum(&self, range: impl std::ops::RangeBounds<usize>) -> T
    where
        T: Clone + Group,
    {
        use std::ops::Bound;
        let start = self.sum_from_start_to(match range.start_bound() {
            Bound::Included(&i) => i,
            Bound::Excluded(i) => i + 1,
            Bound::Unbounded => 0,
        });
        let end = self.sum_from_start_to(match range.end_bound() {
            Bound::Included(i) => i + 1,
            Bound::Excluded(&i) => i,
            Bound::Unbounded => self.cum.len(),
        });
        start.inv().op(&end)
    }
}

impl<T: Group + Clone, I: IntoIterator<Item = T>> From<I> for RangeQ<T> {
    fn from(value: I) -> Self {
        Self::from(value)
    }
}

sum.rs

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Sum(pub i64);

impl Group for Sum {
    fn id() -> Self {
        Sum(0)
    }

    fn op(&self, other: &Self) -> Self {
        Sum(self.0 + other.0)
    }

    fn inv(&self) -> Self {
        Sum(-self.0)
    }
}