Struct seg_tree::segment_tree::LazySegmentTree

pub struct LazySegmentTree<T: LazyNode> { /* private fields */ }

Lazy segment tree with range queries and range updates. It uses O(n) space, assuming that each node uses O(1) space.

Implementations

impl<T: LazyNode + Clone> LazySegmentTree<T>

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

Builds lazy segment tree from slice, each element of the slice will correspond to a leaf of the segment tree. It has time complexity of O(n*log(n)), assuming that combine has constant time complexity.

pub fn update(&mut self, i: usize, j: usize, value: <T as Node>::Value)

Updates the range [i,j] with value. It will panic if i or j is not in [0,n). It has time complexity of O(log(n)), assuming that combine, update_lazy_value and update_lazy_value have constant time complexity.

pub fn query(&mut self, left: usize, right: usize) -> Option<T>

Returns the result from the range [left,right]. It returns None if and only if range is empty. It will panic if left or right are not in [0,n). It has time complexity of O(log(n)), assuming that combine, update_lazy_value and update_lazy_value have constant time complexity.