Trait SegTreeSpec 

pub trait SegTreeSpec {
    type T: Clone;

    const ID: Self::T;

    // Required method
    fn op(a: &mut Self::T, b: &Self::T);
}

Defines the monoid operation and element type for a SegTree.

A “monoid” in abstract algebra is a set equipped with an associative binary operation and an identity element. This trait encapsulates that mathematical structure, allowing SegTree to be generic over any valid monoid.

Requirements

The implementing type must satisfy the monoid laws:

• Identity: For any element a, op(a, ID) = a and op(ID, a) = a
• Associativity: op(a, op(b, c)) = op(op(a, b), c)

Examples

Sum Monoid

use array_range_query::SegTreeSpec;

struct SumSpec;
impl SegTreeSpec for SumSpec {
    type T = i32;
    const ID: Self::T = 0;  // 0 is the identity for addition

    fn op(a: &mut Self::T, b: &Self::T) {
        *a += *b;
    }
}

Min Monoid

use array_range_query::SegTreeSpec;

struct MinSpec;
impl SegTreeSpec for MinSpec {
    type T = i32;
    const ID: Self::T = i32::MAX;  // MAX is the identity for min

    fn op(a: &mut Self::T, b: &Self::T) {
        if *a > *b {
            *a = *b;
        }
    }
}

Required Associated Constants

const ID: Self::T

The identity element for the monoid operation op.

This element must satisfy the identity property: for any element a of type T, op(a, ID) must equal a. Common examples:

• 0 for addition
• 1 for multiplication
• i32::MIN for maximum operations
• i32::MAX for minimum operations

Required Associated Types

type T: Clone

The type of the elements stored and operated on in the segment tree.

This type must implement Clone to allow efficient copying during tree operations.

Required Methods

fn op(a: &mut Self::T, b: &Self::T)

The associative binary operation of the monoid, performed in-place.

This operation must be associative: op(a, op(b, c)) must be equal to op(op(a, b), c) for all valid inputs.

The operation mutates the first parameter a to store the result of combining a with b.

Parameters

• a: The left operand (modified in-place to store the result)
• b: The right operand (read-only)

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<T> SegTreeSpec for SegTreeMaxSpec<T>

where T: Clone + ConstLowerBound + Ord,

const ID: Self::T = <T as ConstLowerBound>::MIN

type T = T

impl<T> SegTreeSpec for SegTreeMinSpec<T>

where T: Clone + ConstUpperBound + Ord,

const ID: Self::T = <T as ConstUpperBound>::MAX

type T = T

impl<T> SegTreeSpec for SegTreeSumSpec<T>

where T: Clone + ConstZero + AddAssign<T>,

const ID: Self::T = <T as ConstZero>::ZERO

type T = T