Struct segment_tree::PrefixPoint
source · pub struct PrefixPoint<N, O>where
O: Commutative<N>,{ /* private fields */ }
Expand description
This data structure allows prefix queries and single element modification.
This tree allocates n * sizeof(N)
bytes of memory, and can be resized.
This data structure is implemented using a Fenwick tree, which is also known as a binary indexed tree.
The similar crate prefix-sum
might also be of interest.
Examples
Showcase of functionality:
use segment_tree::ops::Add;
use segment_tree::PrefixPoint;
let buf = vec![10, 5, 30, 40];
let mut pp = PrefixPoint::build(buf, Add);
// If we query, we get the sum up until the specified value.
assert_eq!(pp.query(0), 10);
assert_eq!(pp.query(1), 15);
assert_eq!(pp.query(2), 45);
assert_eq!(pp.query(3), 85);
// Add five to the second value.
pp.modify(1, 5);
assert_eq!(pp.query(0), 10);
assert_eq!(pp.query(1), 20);
assert_eq!(pp.query(2), 50);
assert_eq!(pp.query(3), 90);
// Multiply every value with 2.
pp.map(|v| *v *= 2);
assert_eq!(pp.query(0), 20);
assert_eq!(pp.query(1), 40);
assert_eq!(pp.query(2), 100);
assert_eq!(pp.query(3), 180);
// Divide with two to undo.
pp.map(|v| *v /= 2);
// Add some more values.
pp.extend(vec![0, 10].into_iter());
assert_eq!(pp.query(0), 10);
assert_eq!(pp.query(1), 20);
assert_eq!(pp.query(2), 50);
assert_eq!(pp.query(3), 90);
assert_eq!(pp.query(4), 90);
assert_eq!(pp.query(5), 100);
// Get the underlying values.
assert_eq!(pp.get(0), 10);
assert_eq!(pp.get(1), 10);
assert_eq!(pp.get(2), 30);
assert_eq!(pp.get(3), 40);
assert_eq!(pp.get(4), 0);
assert_eq!(pp.get(5), 10);
// Remove the last value
pp.truncate(5);
assert_eq!(pp.get(0), 10);
assert_eq!(pp.get(1), 10);
assert_eq!(pp.get(2), 30);
assert_eq!(pp.get(3), 40);
assert_eq!(pp.get(4), 0);
// Get back the original values.
assert_eq!(pp.unwrap(), vec![10, 10, 30, 40, 0]);
You can also use other operators:
use segment_tree::ops::Mul;
use segment_tree::PrefixPoint;
let buf = vec![10, 5, 30, 40];
let mut pp = PrefixPoint::build(buf, Mul);
assert_eq!(pp.query(0), 10);
assert_eq!(pp.query(1), 50);
assert_eq!(pp.query(2), 1500);
assert_eq!(pp.query(3), 60000);
Implementations§
source§impl<N, O: Commutative<N>> PrefixPoint<N, O>
impl<N, O: Commutative<N>> PrefixPoint<N, O>
sourcepub fn build(buf: Vec<N>, op: O) -> PrefixPoint<N, O>
pub fn build(buf: Vec<N>, op: O) -> PrefixPoint<N, O>
Creates a PrefixPoint
containing the given values.
Uses O(len)
time.
sourcepub fn query(&self, i: usize) -> Nwhere
N: Clone,
pub fn query(&self, i: usize) -> Nwhere
N: Clone,
Computes a[0] * a[1] * ... * a[i]
. Note that i
is inclusive.
Uses O(log(i))
time.
sourcepub fn query_noclone(&self, i: usize) -> MaybeOwned<'_, N>
pub fn query_noclone(&self, i: usize) -> MaybeOwned<'_, N>
Computes a[0] * a[1] * ... * a[i]
. Note that i
is inclusive.
Uses O(log(i))
time.
sourcepub fn modify(&mut self, i: usize, delta: N)
pub fn modify(&mut self, i: usize, delta: N)
Combine the value at i
with delta
.
Uses O(log(len))
time.
sourcepub fn truncate(&mut self, size: usize)
pub fn truncate(&mut self, size: usize)
Truncates the PrefixPoint
to the given size. If size >= len
, this method does
nothing. Uses O(1)
time.
sourcepub fn shrink_to_fit(&mut self)
pub fn shrink_to_fit(&mut self)
Calls shrink_to_fit
on the interval vector.
source§impl<N, O: Commutative<N> + Invertible<N>> PrefixPoint<N, O>
impl<N, O: Commutative<N> + Invertible<N>> PrefixPoint<N, O>
sourcepub fn get(&self, i: usize) -> Nwhere
N: Clone,
pub fn get(&self, i: usize) -> Nwhere
N: Clone,
Returns the value at i
.
Uses O(log(i))
time.
Store your own copy of the array if you want constant time.
sourcepub fn set(&mut self, i: usize, value: N)where
N: Clone,
pub fn set(&mut self, i: usize, value: N)where
N: Clone,
Change the value at the index to be the specified value.
Uses O(log(i))
time.
sourcepub fn unwrap_clone(&self) -> Vec<N>where
N: Clone,
pub fn unwrap_clone(&self) -> Vec<N>where
N: Clone,
Compute the underlying array of values.
Uses O(len)
time.
Trait Implementations§
source§impl<N: Clone, O: Commutative<N> + Clone> Clone for PrefixPoint<N, O>
impl<N: Clone, O: Commutative<N> + Clone> Clone for PrefixPoint<N, O>
source§fn clone(&self) -> PrefixPoint<N, O>
fn clone(&self) -> PrefixPoint<N, O>
1.0.0 · source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read moresource§impl<N, O: Commutative<N> + Default> Default for PrefixPoint<N, O>
impl<N, O: Commutative<N> + Default> Default for PrefixPoint<N, O>
source§fn default() -> PrefixPoint<N, O>
fn default() -> PrefixPoint<N, O>
source§impl<N, O: Commutative<N>> Extend<N> for PrefixPoint<N, O>
impl<N, O: Commutative<N>> Extend<N> for PrefixPoint<N, O>
source§fn extend<I: IntoIterator<Item = N>>(&mut self, values: I)
fn extend<I: IntoIterator<Item = N>>(&mut self, values: I)
Adds the given values to the PrefixPoint
, increasing its size.
Uses O(len)
time.
source§fn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
extend_one
)source§fn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one
)