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.
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.
PointSegment data structure allows point queries and interval updates to an
array in logaritmic time.
PrefixPoint data structure is a weaker version of the
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
The segment tree in this crate is inspired by this blog post.
The similar crate
prefix-sum might also be of interest.
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);
Module of operations that can be performed in a segment tree.
This data structure allows range modification and single element queries.
This data structure allows prefix queries and single element modification.
This data structure allows range queries and single element modification.