Crate segment_tree
source ·Expand description
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 interval queries and point updates to an
array in logaritmic time. It is well known for solving the range minimum query
problem. This is the data structure traditionally known as a segment tree.
The PointSegment data structure allows point queries and interval updates to an
array in logaritmic time.
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. However it has the advantage that it uses half the memory and the
size of the array can be changed. This data structure is also known as a
fenwick tree.
The segment tree in this crate is inspired by this blog post.
The similar crate prefix-sum might also be of interest.
This crate has the optional feature num-bigint, which implements the operations in
ops for BigInt and BigUint.
Example
The example below shows a segment tree, which allows queries to any interval in logaritmic time.
use segment_tree::SegmentPoint;
use segment_tree::ops::Min;
let array = vec![4, 3, 2, 1, 2, 3, 4];
let mut tree = SegmentPoint::build(array, Min);
// Compute the minimum of the whole array.
assert_eq!(tree.query(0, tree.len()), 1);
// Compute the minimum of part of the array.
assert_eq!(tree.query(0, 3), 2);
// Change the 1 into a 10.
tree.modify(3, 10);
// The minimum of the whole array is now 2.
assert_eq!(tree.query(0, tree.len()), 2);