Module contest_algorithms::range_query::static_arq

Associative Range Query Tree

Structs

StaticArq

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:

Functions

first_negative

An example of binary search to find the first position whose element is negative. In this case, we use RMQ to locate the leftmost negative element. To ensure the existence of a valid root note (i == 1) from which to descend, the tree's size must be a power of two.