Struct contest_algorithms::arq_tree::ArqTree

pub struct ArqTree<T: ArqSpec> { /* fields omitted */ }

Colloquially known as a "segtree" in the sport programming literature, it represents a sequence of elements a_i (0 <= i < size) from a monoid (M, +) on which we want to support fast range operations:

• modify(l, r, f) replaces a_i (l <= i <= r) by f(a_i) for an endomorphism f
• query(l, r) returns the aggregate a_l + a_{l+1} + ... + a_r

Future work: ArqTree would lend itself naturally to Rust's ownership system. Initially, we should only have access to the root nodes: if size is a power of two, there is a unique root at index 1. arq.push(i) locks i and acquires access to its children. arq.pull(i) is called when the lock on i is released.

Methods

impl<T: ArqSpec> ArqTree<T> where
    T::F: Clone, 

pub fn new(init_val: Vec<T::M>) -> Self

Initializes a static balanced tree on top of the given sequence.

pub fn modify(&mut self, l: usize, r: usize, f: &T::F)

Applies the endomorphism f to all entries from l to r, inclusive. If l == r, the updates are eager. Otherwise, they are lazy.

Panics

Panics if l or r is out of range.

pub fn query(&mut self, l: usize, r: usize) -> T::M

Returns the aggregate range query on all entries from l to r, inclusive.

Panics

Panics if l or r is out of range.