Crate segment_tree [−] [src]
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 solving the range minimum query problem, as
well as performing any operator (such as addition or matrix multiplication) over any interval.
This is the data structure traditionally known as a segment tree.
The PointSegment
data structure allows doing something to every value in some interval
using only logaritmic time. For example add 5
to every value with indices between 5000
and
30000
.
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.
Modules
maybe_owned |
This module contains a variant of |
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. |