segment_tree/lib.rs
1//! This crate contains various data structures useful for quickly performing interval
2//! queries or modifications in some array.
3//!
4//! The data structures in this crate are all trees. The trees are represented using an
5//! array for high performance and low memory usage.
6//! Despite the name of the crate, not every tree in this crate is a segment tree.
7//!
8//! The [`SegmentPoint`] data structure allows interval queries and point updates to an
9//! array in logaritmic time. It is well known for solving the [range minimum query][1]
10//! problem. This is the data structure traditionally known as a segment tree.
11//!
12//! The [`PointSegment`] data structure allows point queries and interval updates to an
13//! array in logaritmic time.
14//!
15//! The [`PrefixPoint`] data structure is a weaker version of the [`SegmentPoint`] data
16//! structure, since the intervals must start at the index `0` and the operator must be
17//! [commutative][2]. However it has the advantage that it uses half the memory and the
18//! size of the array can be changed. This data structure is also known as a
19//! [fenwick tree][3].
20//!
21//! The segment tree in this crate is inspired by [this blog post][4].
22//!
23//! The similar crate [`prefix-sum`] might also be of interest.
24//!
25//! This crate has the optional feature [`num-bigint`], which implements the operations in
26//! [`ops`] for [`BigInt`] and [`BigUint`].
27//!
28//! # Example
29//!
30//! The example below shows a segment tree, which allows queries to any interval in
31//! logaritmic time.
32//!
33//! ```
34//! use segment_tree::SegmentPoint;
35//! use segment_tree::ops::Min;
36//!
37//! let array = vec![4, 3, 2, 1, 2, 3, 4];
38//! let mut tree = SegmentPoint::build(array, Min);
39//!
40//! // Compute the minimum of the whole array.
41//! assert_eq!(tree.query(0, tree.len()), 1);
42//!
43//! // Compute the minimum of part of the array.
44//! assert_eq!(tree.query(0, 3), 2);
45//!
46//! // Change the 1 into a 10.
47//! tree.modify(3, 10);
48//!
49//! // The minimum of the whole array is now 2.
50//! assert_eq!(tree.query(0, tree.len()), 2);
51//! ```
52//!
53//! [1]: https://en.wikipedia.org/wiki/Range_minimum_query
54//! [2]: ops/trait.Commutative.html
55//! [3]: https://en.wikipedia.org/wiki/Fenwick_tree
56//! [4]: https://codeforces.com/blog/entry/18051
57//! [`SegmentPoint`]: struct.SegmentPoint.html
58//! [`PointSegment`]: struct.PointSegment.html
59//! [`PrefixPoint`]: struct.PrefixPoint.html
60//! [`num-bigint`]: https://crates.io/crates/num-bigint
61//! [`BigInt`]: https://docs.rs/num-bigint/0.2/num_bigint/struct.BigInt.html
62//! [`BigUint`]: https://docs.rs/num-bigint/0.2/num_bigint/struct.BigUint.html
63//! [`prefix-sum`]: https://crates.io/crates/prefix-sum
64//! [`ops`]: ops/index.html
65
66pub mod ops;
67pub mod maybe_owned;
68pub use crate::fenwick::PrefixPoint;
69pub use crate::propagating::PointSegment;
70pub use crate::segment_tree::SegmentPoint;
71
72mod fenwick;
73mod propagating;
74mod segment_tree;