Module contest_algorithms::arq_tree

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

Structs

ArqTree	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:
AssignMin	Range Minimum Query (RMQ), a classic application of ARQ. modify(l, r, &f) sets all entries a[l..=r] to f. query(l, r) finds the minimum value in a[l..=r].
AssignSum	Range Sum Query, a slightly trickier classic application of ARQ. modify(l, r, &f) sets all entries a[l..=r] to f. query(l, r) sums all the entries a[l..=r].
SupplyDemand	Supply & Demand, based on https://codeforces.com/gym/102218/problem/F modify(i, i, &(p, o)) increases supply by p and demand by o at time i. query(l, r) computes total supply and demand at times l to r, as well as

Traits

ArqSpec

Functions

first_negative

An example of binary search on an ArqTree. 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 size must be a power of two.