File WordRangeMinimum.h

↰ Parent directory (ADS/search)

The engineered range minimum query, beyond the book [see File RangeMinimum.h for the sparse table and the solution of Bender and Farach-Colton]: the place of the leftmost minimum of A[ i .

Definition (ADS/search/WordRangeMinimum.h)

Detailed Description

. j ], in O( 1 ) time with a few accesses to the memory and O( n ) words of space.

The array is cut into blocks of 64 items, the bits of a word. Inside a block that starts at b, the stack of the minima from the right is kept as a mask for every place j: :math:`[

mathit{mask}[ j ] = sum big{ 2^{t - b} ;:; b le t le j , ; A[ t ] le A[ u ] mbox{ for all } t < u le j big} ,

` i.e., the places on the stack of the scan of the block from b up to j, which pops the items larger than the new one and pushes it. The leftmost minimum of A[ i .. j ] in a block is then the lowest bit of mask[ j ] at or above i, :math:` b + mathrm{ctz}( mathit{mask}[ j ] wedge neg ( 2^{i - b} - 1 ) ) , one count of the trailing zeros: the places of the stack from i on are the minima from the right of A[ i .. j ], increasing, and the first of them is the minimum, the leftmost one since the equal items stay on the stack. A query across blocks takes the minimum of the suffix of the block of i, that of the prefix of the block of j and, if there are blocks in between, that of the two entries of a sparse table on the minima of the blocks that cover them [see SparseTable in :ref:`file_ADS_search_RangeMinimum.h], the leftmost of the smallest of three; the minima of the suffixes and of the prefixes are kept for every place, the value and its offset in the block side by side, and so are the minima in the table, so that a query makes at most five reads of the memory, independent of one another, and never reads the array; the minima are chosen by conditional moves, which a random range would mispredict as branches half of the times.

The masks are built by the stacks in O( n ) time, or on the integers and the floating types under std::less by one comparison of vectors of the block per item [see greaterBits() in File CountLess.h], the larger items cleared from the mask of the item before all at once, :math:` mathit{mask}[ j ] = ( mathit{mask}[ j - 1 ] wedge neg G_j ) vee 2^{j - b} ` with :math:` G_j ` the bits of the items of the block larger than A[ j ] (the stack is increasing, so the items it pops are exactly those of it larger than A[ j ]), with no branch. The space is :math:`[

n big( 8 + 2 , mathit{sizeof}( T ) + 2 big) + Biglceil frac{n}{64} Bigrceil Biglceil log_2 Biglceil frac{n}{64} Bigrceil Bigrceil big( mathit{sizeof}( T ) + 4 big)

` bytes besides the array (the masks, the minima of the suffixes and of the prefixes with their offsets, and the table), on huge pages [see File HugePageAllocator.h]: about 20 bytes per item of 32 bits, against the :math:` 4 lceil log_2 n rceil ` bytes of a sparse table on all the items (80 for a million).

Compared with the literature: the masks are the in-word stacks of the practical solutions that came after the succinct one of Fischer and Heun (who encode the Cartesian tree of each block in 2 n + o( n ) bits and answer through a table of the shapes of the trees), e.g., the structure of Baumstark, Gog, Heuer and Labeit, which trade those bits for a query that touches one or two words; the decomposition into blocks with a sparse table on their minima is that of Bender and Farach-Colton.

The contracts [see File Contract.h]: fewer than :math:` 2^{32} ` items; a query asks for i <= j < n, and its answer is a leftmost minimum of the range, an audit. The functions are defined in WordRangeMinimum.tpp.

  1. Fischer, V. Heun, Space-efficient preprocessing schemes for range minimum queries on static arrays, SIAM Journal on Computing 40(2), 465-492, 2011, doi:10.1137/090779759

    1. Bender, M. Farach-Colton, The LCA problem revisited, Proceedings of LATIN 2000, LNCS 1776, 88-94, 2000, doi:10.1007/10719839_9

  2. Baumstark, S. Gog, T. Heuer, J. Labeit, Practical range minimum queries revisited, Proceedings of SEA 2017, LIPIcs 75, 12:1-12:16, 2017, doi:10.4230/LIPIcs.SEA.2017.12

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes