Struct SegmentTree 

pub struct SegmentTree<T> { /* private fields */ }

Available on crate feature monoid only.

SegmentTree is a data structure for efficient range queries based on perfect binary tree. It requires the underlying operation on the data to form a Monoid.

Examples

use semigroup::{op::Sum, segment_tree::SegmentTree};
let data = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let mut sum_tree: SegmentTree<_> = data.into_iter().map(Sum).collect();
assert_eq!(sum_tree.fold(3..=5).0, 12);
sum_tree.update(4, 8.into());
assert_eq!(sum_tree.fold(3..=5).0, 16);

Implementations

impl<T> SegmentTree<T>

pub fn get<I: SegmentTreeIndex<T>>(&self, index: I) -> Option<&I::Output>

O(1), get element(s) by index like Vec.

impl<T> SegmentTree<T>

pub fn iter<'a>(&'a self) -> Iter<'a, T>

O(1), get iterator of the segment tree leaf.

impl<T> SegmentTree<T>

pub fn new() -> Self

O(1), init empty segment tree.

pub fn len(&self) -> usize

O(1), return this segment tree’s number of data.

pub fn is_empty(&self) -> bool

O(1), check if this segment tree is empty.

impl<T: Monoid + Clone> SegmentTree<T>

pub fn update(&mut self, i: usize, x: T) -> Option<T>

O(log(n)), set leaf[i] = x, and update segment tree.

pub fn update_with<F>(&mut self, i: usize, f: F) -> Option<T>

where F: FnOnce(&T) -> T,

O(log(n)), update leaf[i] by f(leaf[i]), and update segment tree.

pub fn push(&mut self, x: T)

amortized O(log(n)), push x to the segment tree, when construct new segment tree should be used Self::from or Self::from_iter (std::iter::Iterator::collect) instead.

pub fn extend_from_slice(&mut self, slice: &[T])

amortized O(len(slice) log(n)), extend segment tree by given slice.

pub fn fold<R>(&self, range: R) -> T

where R: RangeBounds<usize>,

O(log(n)), fold the range.

pub fn bisect_left<R, F>(&self, range: R, cmp: F) -> Option<usize>

where R: RangeBounds<usize>, F: Fn(&T) -> bool,

O(log^2(n)), search the leftmost leaf where cmp(x) is true in the range.

pub fn bisect_right<R, F>(&self, range: R, cmp: F) -> Option<usize>

where R: RangeBounds<usize>, F: Fn(&T) -> bool,

O(log^2(n)), search the rightmost leaf where cmp(x) is true in the range.

Trait Implementations

impl<T: Clone> Clone for SegmentTree<T>

fn clone(&self) -> SegmentTree<T>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for SegmentTree<T>

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

Formats the value using the given formatter.

impl<T: Default> Default for SegmentTree<T>

fn default() -> SegmentTree<T>

Returns the “default value” for a type.

impl<T: Monoid + Clone> Extend<T> for SegmentTree<T>

fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T: Monoid + Clone> From<Vec<T>> for SegmentTree<T>

fn from(v: Vec<T>) -> Self

Converts to this type from the input type.

impl<T: Monoid + Clone> FromIterator<T> for SegmentTree<T>

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator.

impl<T: Hash> Hash for SegmentTree<T>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<T, I: SegmentTreeIndex<T>> Index<I> for SegmentTree<T>

type Output = <I as SegmentTreeIndex<T>>::Output

The returned type after indexing.

fn index(&self, index: I) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<'a, T> IntoIterator for &'a SegmentTree<T>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> IntoIterator for SegmentTree<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: PartialEq> PartialEq for SegmentTree<T>

fn eq(&self, other: &SegmentTree<T>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: Eq> Eq for SegmentTree<T>

impl<T> StructuralPartialEq for SegmentTree<T>