Struct segment_tree::SegmentPoint

source ·

pub struct SegmentPoint<N, O>where
    O: Operation<N>,{ /* private fields */ }

Expand description

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 example solves the range minimum query problem.

use segment_tree::SegmentPoint;
use segment_tree::ops::Min;

// Let's solve the range minimum query on this array.
let mut tree = SegmentPoint::build(
    vec![10i32, 5, 6, 4, 12, 8, 9, 3, 2, 1, 5], Min
); //        0  1  2  3   4  5  6  7  8  9 10  - indices

// Find the minimum value in a few intervals. Note that the second argument is
// exclusive.
assert_eq!(tree.query(0, 2), 5);
assert_eq!(tree.query(4, 8), 3);
assert_eq!(tree.query(3, 11), 1);
assert_eq!(tree.query(0, 11), 1);

// query returns the identity if given an invalid interval
// The identity of min is the MAX.
assert_eq!(tree.query(4, 2), std::i32::MAX);

// We can change individual values in the array as well.
tree.modify(2, 0);
assert_eq!(tree.query(0, 3), 0);
assert_eq!(tree.query(3, 6), 4);

// We can view the values currently stored at any time.
assert_eq!(tree.view(), &[10, 5, 0, 4, 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;

let mut tree = SegmentPoint::build(
    vec![10, 5, 6, 4, 12, 8, 9, 3, 2, 1, 5], Add
); //     0  1  2  3   4  5  6  7  8  9 10  - indices

assert_eq!(tree.query(4, 8), 12 + 8 + 9 + 3);
assert_eq!(tree.query(1, 3), 5 + 6);

// we can still modify values in the tree
tree.modify(2, 4);
assert_eq!(tree.query(1, 3), 5 + 4);
assert_eq!(tree.query(4, 8), 12 + 8 + 9 + 3);

assert_eq!(tree.view(), &[10, 5, 4, 4, 12, 8, 9, 3, 2, 1, 5]);

Implementations§

source §

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

source

pub fn build(buf: Vec<N>, op: O) -> 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.

pub 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.

source

pub fn query(&self, l: usize, r: usize) -> Nwhere
O: Commutative<N> + Identity<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_noiden or query_noclone for a version that works with non-commutative operations.

source

pub fn compose(&mut self, p: usize, delta: &N)where
O: Commutative<N>,

Combine the value at p with delta. Uses O(log(len)) time.

source

pub 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.

source

pub 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.

source

pub fn view(&self) -> &[N] ⓘ

View the values in this segment tree using a slice. Uses O(1) time.

source

pub fn len(&self) -> usize

The number of elements stored in this segment tree. Uses O(1) time.

source

pub fn build_noalloc(buf: Vec<N>, op: O) -> 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::build(
    vec![1, 2, 3, 4], Min
);
// make a segment point using the build_noalloc method:
let mut tree1 = SegmentPoint::build_noalloc(
    // the first half of the values are ignored
    vec![3282, 210, 0, 245, 1, 2, 3, 4], Min
);
assert_eq!(tree, tree1);

let mut tree2 = SegmentPoint::build_noalloc(
    // we can also try some other first few values
    vec![0, 0, 0, 0, 1, 2, 3, 4], Min
);
assert_eq!(tree1, tree2);
assert_eq!(tree, tree2);