# 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);
```