Struct segment_tree::PointSegment
source · pub struct PointSegment<N, O>where
O: Commutative<N> + Identity<N>,{ /* private fields */ }
Expand description
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§
source§impl<N, O: Commutative<N> + Identity<N>> PointSegment<N, O>
impl<N, O: Commutative<N> + Identity<N>> PointSegment<N, O>
sourcepub fn build(buf: Vec<N>, op: O) -> 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.
sourcepub fn build_slice(buf: &[N], op: O) -> PointSegment<N, O>where
N: Clone,
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.
sourcepub fn build_iter<I: ExactSizeIterator<Item = N>>(
iter: I,
op: O
) -> PointSegment<N, O>
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.
sourcepub fn modify(&mut self, l: usize, r: usize, delta: N)
pub fn modify(&mut self, l: usize, r: usize, delta: N)
Combine every value in the interval with delta
.
Uses O(log(len))
time.
Trait Implementations§
source§impl<N: Clone, O: Identity<N> + Commutative<N> + Clone> Clone for PointSegment<N, O>
impl<N: Clone, O: Identity<N> + Commutative<N> + Clone> Clone for PointSegment<N, O>
source§fn clone(&self) -> PointSegment<N, O>
fn clone(&self) -> PointSegment<N, O>
Returns a copy of the value. Read more
1.0.0 · source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
Performs copy-assignment from
source
. Read moresource§impl<N, O: Identity<N> + Commutative<N> + Default> Default for PointSegment<N, O>
impl<N, O: Identity<N> + Commutative<N> + Default> Default for PointSegment<N, O>
source§fn default() -> PointSegment<N, O>
fn default() -> PointSegment<N, O>
Returns the “default value” for a type. Read more