Struct PrefixPoint

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

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

impl<N, O: Commutative<N>> 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.

pub fn len(&self) -> usize

Returns the number of values in this tree. Uses O(1) time.

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

where N: Clone,

Computes a[0] * a[1] * ... * a[i]. Note that i is inclusive. Uses O(log(i)) time.

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.

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

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

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.

pub fn shrink_to_fit(&mut self)

Calls shrink_to_fit on the interval vector.

pub fn map<F: FnMut(&mut N)>(&mut self, f: F)

Replace every value in the type with f(value). This function assumes that combine(f(a), f(b)) = f(combine(a, b)).

The function is applied len times.

impl<N, O: Commutative<N> + Invertible<N>> PrefixPoint<N, O>

pub fn get(&self, i: usize) -> N

where N: Clone,

Returns the value at i. Uses O(log(i)) time. Store your own copy of the array if you want constant time.

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.

pub fn unwrap(self) -> Vec<N>

Compute the underlying array of values. Uses O(len) time.

pub fn unwrap_clone(&self) -> Vec<N>

where N: Clone,

Compute the underlying array of values. Uses O(len) time.

Trait Implementations

impl<N: Clone, O: Commutative<N> + Clone> Clone for PrefixPoint<N, O>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<N, O: Commutative<N> + Default> Default for PrefixPoint<N, O>

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

Returns the “default value” for a type.

impl<N, O: Commutative<N>> Extend<N> for PrefixPoint<N, O>

fn extend<I: IntoIterator<Item = N>>(&mut self, values: I)

Adds the given values to the PrefixPoint, increasing its size. Uses O(len) time.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<'a, N: 'a + Hash, O: Commutative<N>> Hash for PrefixPoint<N, O>

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.