Struct segment_tree::PrefixPoint

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

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.

Examples

Showcase of functionality:

use segment_tree::ops::Add;
use segment_tree::PrefixPoint;

let buf = vec![10, 5, 30, 40];

let mut pp: PrefixPoint<_, Add> = PrefixPoint::build(buf);

 // 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.append(vec![0, 10]);
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 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<_, Mul> = PrefixPoint::build(buf);

assert_eq!(pp.query(0), 10);
assert_eq!(pp.query(1), 50);
assert_eq!(pp.query(2), 1500);
assert_eq!(pp.query(3), 60000);

Methods

impl<N, O: CommutativeOperation<N>> PrefixPoint<N, O>

fn build(buf: Vec<N>) -> PrefixPoint<N, O>

Creates a PrefixPoint containing the given values. Uses O(len) time.

fn len(&self) -> usize

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

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.

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

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

fn truncate(&mut self, size: usize)

Truncates the PrefixPoint to the given size. If size >= len, this method does nothing. Uses O(1) time.

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

Replace every value in the type with f(value). This function assumes that f(a) * f(b) = f(a * b). Applies the function len times.

fn append(&mut self, values: Vec<N>)

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

impl<N, O: CommutativeOperation<N> + Inverse<N>> PrefixPoint<N, O>

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.

fn unwrap(self) -> Vec<N>

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

Trait Implementations

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

impl<N: Clone, O: CommutativeOperation<N>> 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: CommutativeOperation<N>> Default for PrefixPoint<N, O>

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

Returns the "default value" for a type.

impl<'a, N: 'a + Hash, O: CommutativeOperation<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, 

Feeds a slice of this type into the given [Hasher].