Class PlusMinusOneRangeMinimum

• Defined in File RangeMinimum.h

Class Documentation

class PlusMinusOneRangeMinimum

the range minima of an array whose adjacent items differ by 1

Public Functions

PlusMinusOneRangeMinimum(void) = default

explicit PlusMinusOneRangeMinimum(std::vector<long> D)

the blocks, their sparse table and the table of the signatures, O( n )

Pre:

| D[ i + 1 ] - D[ i ] | = 1 for every i

std::size_t query(std::size_t i, std::size_t j) const

the place of the leftmost minimum of D[ i .

. j ], O( 1 )

Pre:

i <= j < size()

Post:

a leftmost minimum of D[ i .. j ] (an audit)

inline std::size_t size(void) const

inline std::size_t blockSize(void) const

the number of items in a block