Struct contest_algorithms::range_query::static_arq::StaticArq

pub struct StaticArq<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 (S, +) on which we want to support fast range operations:

• update(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

This compact representation is based on a [blog post by Al.Cash] (http://codeforces.com/blog/entry/18051). All nodes have 0 or 2 children. Hence, trees whose size is not a power of two will have multiple roots.

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.

Implementations

impl<T: ArqSpec> StaticArq<T>

pub fn new(init_val: &[T::S]) -> Self

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

pub fn update(&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 r >= size. Note that l > r is valid, meaning an empty range.

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

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

Panics

Panics if r >= size. Note that l > r is valid, meaning an empty range.