3 stable releases
|2.0.0||Dec 28, 2018|
|1.1.0||Aug 26, 2017|
|1.0.0||Aug 26, 2017|
#781 in Data structures
1,655 downloads per month
Used in 7 crates (2 directly)
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.
[dependencies] segment-tree = "2"
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);
This crate also has a
PointSegment type, which instead allows modifications to
The related crate
prefix_sum might also be of interest.