Trait LazySegTreeSpec 

pub trait LazySegTreeSpec {
    type T: Clone;
    type U: Clone;

    const ID: Self::T;

    // Required methods
    fn op_on_data(d1: &mut Self::T, d2: &Self::T);
    fn op_on_update(u1: &mut Self::U, u2: &Self::U);
    fn op_update_on_data(u: &Self::U, d: &mut Self::T, size: usize);
}

Specification for lazy segment tree operations.

Defines the data type T, update type U, and three operations that must satisfy:

• Data operation: associative with identity ID
• Update composition: associative (for overlapping updates)
• Update application: correctly accounts for range size

Example

use array_range_query::LazySegTreeSpec;

struct RangeAddSum;
impl LazySegTreeSpec for RangeAddSum {
    type T = i64;
    type U = i64;
    const ID: Self::T = 0;

    fn op_on_data(d1: &mut Self::T, d2: &Self::T) { *d1 += *d2; }
    fn op_on_update(u1: &mut Self::U, u2: &Self::U) { *u1 += *u2; }
    fn op_update_on_data(u: &Self::U, d: &mut Self::T, size: usize) {
        *d += u * size as i64;
    }
}

Required Associated Constants

const ID: Self::T

Identity element for data aggregation.

Required Associated Types

type T: Clone

Data type stored in tree nodes.

type U: Clone

Update type for lazy propagation.

Required Methods

fn op_on_data(d1: &mut Self::T, d2: &Self::T)

Combines two data values in-place (associative operation).

fn op_on_update(u1: &mut Self::U, u2: &Self::U)

Composes two updates in-place (associative operation).

fn op_update_on_data(u: &Self::U, d: &mut Self::T, size: usize)

Applies update to data value, accounting for range size.

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