Struct segment_tree::SegmentPoint
[−]
[src]
pub struct SegmentPoint<N, O> where
O: Operation<N>, { /* fields omitted */ }
This data structure allows range queries and single element modification.
This tree allocates 2n * sizeof(N)
bytes of memory.
This tree is implemented using a segment tree. A segment tree is a binary tree where each node contains the combination of the children under the operation.
Examples
This data structure allows solving the range minimum query problem in logaritmic time.
use segment_tree::SegmentPoint; use segment_tree::ops::Min; // make a segment point let mut tree: SegmentPoint<_, Min> = SegmentPoint::build( vec![10, 5, 6, 4, 12, 8, 9, 3, 2, 1, 5] ); // 0 1 2 3 4 5 6 7 8 9 10 - indices // find the minimum value in a few intervals assert_eq!(tree.query(0, 2), Some(5)); assert_eq!(tree.query(4, 8), Some(3)); assert_eq!(tree.query(3, 11), Some(1)); assert_eq!(tree.query(0, 11), Some(1)); // query returns None if given an invalid interval assert_eq!(tree.query(4, 2), None); // if we want to avoid cloning, we can use noclone_query: use segment_tree::maybe_owned::MaybeOwned; assert_eq!(tree.noclone_query(4, 9), Some(MaybeOwned::Owned(2))); // note that the Eq implementation of MaybeOwned considers Owned and Borrowed equal if their // contents are equal // since minimum is commutative, we can use quick_query assert_eq!(tree.quick_query(3, 11), 1); // let's update a few values tree.modify(1, 3); assert_eq!(tree.quick_query(0, 2), 3); assert_eq!(tree.quick_query(5, 8), 3); tree.modify(3, 0); assert_eq!(tree.quick_query(2, 8), 0); // we can view the values currently stored at any time assert_eq!(tree.view(), &[10, 3, 6, 0, 12, 8, 9, 3, 2, 1, 5]);
We can also use a SegmentPoint
to find the sum of any interval, by changing the operator to
Add
.
use segment_tree::SegmentPoint; use segment_tree::ops::Add; // make a segment point let mut tree: SegmentPoint<_, Add> = SegmentPoint::build( vec![10, 5, 6, 4, 12, 8, 9, 3, 2, 1, 5] ); // 0 1 2 3 4 5 6 7 8 9 10 - indices assert_eq!(tree.quick_query(4, 8), 12 + 8 + 9 + 3); assert_eq!(tree.quick_query(1, 3), 5 + 6); // quick_query returns the identity if given an invalid interval assert_eq!(tree.quick_query(3, 1), 0); // we can still modify values in the tree tree.modify(2, 4); assert_eq!(tree.quick_query(1, 3), 5 + 4); assert_eq!(tree.quick_query(4, 8), 12 + 8 + 9 + 3); assert_eq!(tree.view(), &[10, 5, 4, 4, 12, 8, 9, 3, 2, 1, 5]);
Methods
impl<N, O: Operation<N>> SegmentPoint<N, O>
[src]
fn build(buf: Vec<N>) -> SegmentPoint<N, O> where
N: Clone,
N: Clone,
Builds a tree using the given buffer. If the given buffer is less than half full, this
function allocates. This function clones every value in the input array.
Uses O(len)
time.
See also the function build_noalloc
.
fn query(&self, l: usize, r: usize) -> Option<N> where
N: Clone,
N: Clone,
Computes a[l] * a[l+1] * ... * a[r-1]
.
If l >= r
, this method returns None
. This method clones at most twice and runs in
O(log(len))
time.
See quick_query
or noclone_query
for a version that doesn't clone.
fn noclone_query<'a>(&'a self, l: usize, r: usize) -> Option<MaybeOwned<'a, N>>
Computes a[l] * a[l+1] * ... * a[r-1]
.
If l >= r
, this method returns None
.
Uses O(log(len))
time.
See also query
and quick_query
.
fn modify(&mut self, p: usize, value: N) -> N
Set the value at the specified index and return the old value.
Uses O(log(len))
time.
fn compose_left(&mut self, p: usize, delta: &N)
Combine the value at p
with delta
, such that delta
is the left argument.
Uses O(log(len))
time.
fn compose_right(&mut self, p: usize, delta: &N)
Combine the value at p
with delta
, such that delta
is the right argument.
Uses O(log(len))
time.
fn view(&self) -> &[N]
View the values in this segment tree using a slice. Uses O(1)
time.
fn len(&self) -> usize
The number of elements stored in this segment tree. Uses O(1)
time.
fn build_noalloc(buf: Vec<N>) -> SegmentPoint<N, O>
Builds a tree using the given buffer. The buffer must be even in size.
The first n
values have no effect on the resulting tree,
and the remaining n
values contains the array to build the tree on.
Uses O(len)
time.
This function panics if the size of the buffer is odd.
Example
use segment_tree::SegmentPoint; use segment_tree::ops::Min; // make a segment point using the other build method let mut tree: SegmentPoint<_, Min> = SegmentPoint::build( vec![1, 2, 3, 4] ); // make a segment point using the build_noalloc method: let mut tree1: SegmentPoint<_, Min> = SegmentPoint::build_noalloc( vec![3282, 210, 0, 245, 1, 2, 3, 4] // the first half of the values are ignored ); assert_eq!(tree, tree1); let mut tree2: SegmentPoint<_, Min> = SegmentPoint::build_noalloc( vec![0, 0, 0, 0, 1, 2, 3, 4] // we can also try some other first few values ); assert_eq!(tree1, tree2); assert_eq!(tree, tree2);
impl<N, O: CommutativeOperation<N>> SegmentPoint<N, O>
[src]
fn compose(&mut self, p: usize, delta: &N)
Combine the value at p
with delta
.
Uses O(log(len))
time.
impl<N, O: CommutativeOperation<N> + Identity<N>> SegmentPoint<N, O>
[src]
fn quick_query(&self, l: usize, r: usize) -> N
Computes a[l] * a[l+1] * ... * a[r-1]
.
Uses O(log(len))
time.
If l >= r
, this method returns the identity.
See query
or noclone_query
for a version that works with non-commutative operations.
Trait Implementations
impl<N: Clone, O: Operation<N>> Clone for SegmentPoint<N, O>
[src]
fn clone(&self) -> SegmentPoint<N, O>
Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0
Performs copy-assignment from source
. Read more
impl<N: Debug, O: Operation<N>> Debug for SegmentPoint<N, O>
[src]
impl<N: PartialEq, O: Operation<N>> PartialEq for SegmentPoint<N, O>
[src]
fn eq(&self, other: &SegmentPoint<N, O>) -> bool
This method tests for self
and other
values to be equal, and is used by ==
. Read more
fn ne(&self, other: &SegmentPoint<N, O>) -> bool
This method tests for !=
.
impl<N: Eq, O: Operation<N>> Eq for SegmentPoint<N, O>
[src]
impl<N, O: Operation<N>> Default for SegmentPoint<N, O>
[src]
fn default() -> SegmentPoint<N, O>
Returns the "default value" for a type. Read more