Module contest_algorithms::range_query::static_arq

Associative Range Query Tree based on [Al.Cash's compact representation] (http://codeforces.com/blog/entry/18051).

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

Functions

first_negative

An example of binary search on the tree of a StaticArq. 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.