Struct LazySegTree 

pub struct LazySegTree<Spec: LazySegTreeSpec> { /* private fields */ }

Implementations

impl<Spec: LazySegTreeSpec> LazySegTree<Spec>

pub fn new(size: usize) -> Self

Creates a new lazy segment tree with all values initialized to Spec::ID.

Time Complexity

O(n)

Panics

Panics if size is 0.

pub fn from_slice(values: &[Spec::T]) -> Self

Creates a new lazy segment tree from a slice of values.

Time Complexity

O(n)

Panics

Panics if values is empty.

pub fn from_vec(values: Vec<Spec::T>) -> Self

Creates a new lazy segment tree from a vector of values.

Time Complexity

O(n)

Panics

Panics if values is empty.

pub fn query<R: RangeBounds<usize>>(&self, range: R) -> Spec::T

Queries the aggregated value over the given range.

Example

use array_range_query::helpers::LazySegTreeAddMax;

let mut tree = LazySegTreeAddMax::<i32>::from_vec(vec![1, 2, 3, 4, 5]);
assert_eq!(tree.query(0..=4), 5);

Time Complexity

O(log n)

Panics

Panics if the range is invalid or out of bounds.

pub fn update<R: RangeBounds<usize>>(&mut self, range: R, value: Spec::U)

Applies an update to all elements in the given range.

Example

use array_range_query::helpers::LazySegTreeAddMax;

let mut tree = LazySegTreeAddMax::<i32>::from_vec(vec![1, 2, 3, 4, 5]);
tree.update(1..=3, 10);
assert_eq!(tree.query(..), 14);

Time Complexity

O(log n)

Panics

Panics if the range is invalid or out of bounds.

Trait Implementations

impl<Spec: Clone + LazySegTreeSpec> Clone for LazySegTree<Spec>

where Spec::T: Clone, Spec::U: Clone,

fn clone(&self) -> LazySegTree<Spec>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<Spec: Debug + LazySegTreeSpec> Debug for LazySegTree<Spec>

where Spec::T: Debug, Spec::U: Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<Spec: LazySegTreeSpec> Display for LazySegTree<Spec>

where Spec::T: Display + PartialEq, Spec::U: Display,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.