1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
//! This crate contains various data structures useful for quickly performing interval queries or //! modifications in some array. //! //! The data structures in this crate are all trees. The trees are represented using an array for //! high performance and low memory usage. //! Despite the name of the crate, not every tree in this crate is a segment tree. //! //! The [`SegmentPoint`] data structure allows solving the [range minimum query][1] problem, as //! well as performing any operator (such as addition or matrix multiplication) over any interval. //! This is the data structure traditionally known as a segment tree. //! //! The [`PointSegment`] data structure allows doing something to every value in some interval //! using only logaritmic time. For example add `5` to every value with indices between `5000` and //! `30000`. //! //! The [`PrefixPoint`] data structure is a weaker version of the [`SegmentPoint`] data structure, //! since the intervals must start at the index `0` and the operator must be [commutative][2]. //! However it has the advantage that it uses half the memory and the size of the array can be //! changed. //! //! [1]: https://en.wikipedia.org/wiki/Range_minimum_query //! [2]: ops/trait.CommutativeOperation.html //! [`SegmentPoint`]: struct.SegmentPoint.html //! [`PointSegment`]: struct.PointSegment.html //! [`PrefixPoint`]: struct.PrefixPoint.html pub mod ops; pub mod maybe_owned; pub use fenwick::PrefixPoint; pub use propogating::PointSegment; pub use range_query::SegmentPoint; mod fenwick; mod propogating; mod range_query; #[cfg(test)] extern crate rand;