Crate segment_tree

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

Modules

maybe_owned

This module contains a variant of Cow that doesn’t require Clone.

ops

Module of operations that can be performed in a segment tree.

Structs

PointSegment

This data structure allows range modification and single element queries.

PrefixPoint

This data structure allows prefix queries and single element modification.

SegmentPoint

This data structure allows range queries and single element modification.