Struct seg_tree::segment_tree::PersistentSegmentTree

pub struct PersistentSegmentTree<T: PersistentNode> { /* private fields */ }

Persistent segment tree, it saves every version of itself, it has range queries and point updates. It uses O(n+q*log(n)) space, where q is the amount of updates, and assuming that each node uses O(1) space.

Implementations

impl<T> PersistentSegmentTree<T> where
    T: PersistentNode + Clone, 

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

Builds persistent 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 query(&self, version: usize, left: usize, right: usize) -> Option<T>

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

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

Creates a new segment tree version from version were the p-th element of the segment tree to value T and update the segment tree correspondingly. It will panic if p is not in [0,n), or if version is not in [0,versions). It has time complexity of O(log(n)), assuming that combine has constant time complexity.

pub fn versions(&self) -> usize

Return the amount of different versions the current segment tree has.