Struct seg_tree::segment_tree::SegmentTree

pub struct SegmentTree<T: Node + Clone> { /* private fields */ }

Segment tree with range queries and point updates. It uses O(n) space, assuming that each node uses O(1) space. Note if you need to use lower_bound, just use the RecursiveSegmentTree it uses double the memory though and it’s less performant.

Implementations

impl<T> SegmentTree<T> where
    T: Node + Clone, 

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

Builds 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, value: <T as Node>::Value)

Sets the i-th element of the segment tree to value T and update the segment tree correspondingly. It will panic if i is not in [0,n) It has time complexity of O(log(n)), assuming that combine has constant time complexity.

pub fn query(&self, l: usize, r: 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 has constant time complexity.