Struct segment_tree::PointSegment

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

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<_, Add> = PointSegment::build(repeat(0).take(1_000_000).collect());

 // add one to every value between 200 and 1000
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);

Methods

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

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

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

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

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

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

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

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

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

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

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.

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> + CommutativeOperation<N>> 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> + CommutativeOperation<N>> Default for PointSegment<N, O>

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

Returns the "default value" for a type.