Struct PointSegment

pub struct PointSegment<N, O>
where
    O: Commutative<N> + Identity<N>,
{ /* private fields */ }

This data structure allows range modification and single element queries.

This tree allocates 2n * sizeof(N) bytes of memory.

This tree is implemented using a binary tree, where each node contains the changes that need to be propogated to its children.

Examples

Quickly add something to every value in some interval.

use segment_tree::PointSegment;
use segment_tree::ops::Add;

use std::iter::repeat;

// make a giant tree of zeroes
let mut tree = PointSegment::build(repeat(0).take(1_000_000).collect(), Add);

// add one to every value between 200 and 500000
tree.modify(200, 500_000, 1);
assert_eq!(tree.query(100), 0);
assert_eq!(tree.query(200), 1);
assert_eq!(tree.query(500), 1);
assert_eq!(tree.query(499_999), 1);
assert_eq!(tree.query(500_000), 0);

// add five to every value between 0 and 1000
tree.modify(0, 1000, 5);
assert_eq!(tree.query(10), 5);
assert_eq!(tree.query(500), 6);
assert_eq!(tree.query(10_000), 1);
assert_eq!(tree.query(600_000), 0);

Implementations

impl<N, O: Commutative<N> + Identity<N>> PointSegment<N, O>

pub fn build(buf: Vec<N>, op: O) -> PointSegment<N, O>

Builds a tree using the given buffer. If the given buffer is less than half full, this function allocates. Uses O(len) time.

pub fn build_slice(buf: &[N], op: O) -> PointSegment<N, O>

where N: Clone,

Allocate a new buffer and build the tree using the values in the slice. Uses O(len) time.

pub fn build_iter<I: ExactSizeIterator<Item = N>>( iter: I, op: O, ) -> PointSegment<N, O>

Allocate a new buffer and build the tree using the values in the iterator. Uses O(len) time.

pub fn query(&self, p: usize) -> N

Computes the value at p. Uses O(log(len)) time.

pub fn modify(&mut self, l: usize, r: usize, delta: N)

Combine every value in the interval with delta. Uses O(log(len)) time.

pub fn propogate(&mut self) -> &mut [N]

Propogate all changes to the leaves in the tree and return a mutable slice containing the leaves.

Uses O(len) time.

pub fn len(&self) -> usize

Returns the number of values in the underlying array. Uses O(1) time.

Trait Implementations

impl<N: Clone, O: Identity<N> + Commutative<N> + Clone> Clone for PointSegment<N, O>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<N, O: Identity<N> + Commutative<N> + Default> Default for PointSegment<N, O>

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

Returns the “default value” for a type.