Struct segment_tree::SegmentPoint

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>

fn build(buf: Vec<N>) -> SegmentPoint<N, O> where
    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, 

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>

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>

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>

fn clone(&self) -> SegmentPoint<N, O>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<N: Debug, O: Operation<N>> Debug for SegmentPoint<N, O>

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<N: PartialEq, O: Operation<N>> PartialEq for SegmentPoint<N, O>

fn eq(&self, other: &SegmentPoint<N, O>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &SegmentPoint<N, O>) -> bool

This method tests for !=.

impl<N: Eq, O: Operation<N>> Eq for SegmentPoint<N, O>

impl<N, O: Operation<N>> Default for SegmentPoint<N, O>

fn default() -> SegmentPoint<N, O>

Returns the "default value" for a type.

impl<'a, N: 'a + Hash, O: Operation<N>> Hash for SegmentPoint<N, O>

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given [Hasher].

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given [Hasher].