File RangeMinimum.h

↰ Parent directory (ADS/search)

The range minimum query, beyond the book: given an array A of n items of an ordered universe, the place of a minimum of A[ i .

Definition (ADS/search/RangeMinimum.h)

Detailed Description

. j ] for any i <= j, the leftmost one when the minimum repeats. The problem is the backbone of the longest common extensions of a text [see File SuffixArray.h] and of the lowest common ancestors of a tree [see File SuffixTree.h].

  • SparseTable stores, for every place i and every L, the place of the minimum of A[ i .. i + 2^L - 1 ], computed from the two halves of the range; a query covers [ i , j ] by the two (possibly overlapping) ranges of length :math:` 2^L , :math: L = lfloor log_2( j - i + 1 ) rfloor , that start at i and end at j. It takes :math: O( n log n ) ` time and space and answers in O( 1 ) time, against the :math:` O( n^2 ) ` of the table of all the answers.

  • cartesianTree() builds the Cartesian tree of A with a stack in O( n ): its root is the leftmost minimum of A, its left and right subtrees the Cartesian trees of the parts before and after it; a range of A is a subtree, and the minimum of A[ i .. j ] is the lowest common ancestor of i and j.

  • PlusMinusOneRangeMinimum answers the queries on an array whose adjacent items differ by exactly 1, as the depths along an Euler tour of a tree: the array is cut into blocks of :math:` d = max{ 1 , lfloor log_2 n rfloor / 2 } ` items, a sparse table on the minima of the blocks answers for the blocks covered entirely, and a block is described by the d - 1 signs of its differences, so that a table of the :math:` 2^{d-1} le sqrt{n} ` signatures times the :math:` d^2 ` pairs of offsets (the trick of the Four Russians) answers inside a block: O( n ) time and space, O( 1 ) time per query.

  • RangeMinimum is the solution of Bender and Farach-Colton for any array: the minimum of A[ i .. j ] is the lowest common ancestor of i and j in the Cartesian tree, i.e., the node of least depth on the Euler tour of the tree between the first visits of i and j, a query on the 2 n - 1 depths of the tour, which differ by 1. Its time and space are O( n ), O( 1 ) time per query (Theorem 10.11), and the same reduction answers the lowest common ancestors of any tree (Theorem 10.12).

The bound O( n ) of Bender and Farach-Colton was first reached by Harel and Tarjan on the lowest common ancestors, with a far more involved structure; Fischer and Heun need only 2 n + o( n ) bits besides A, by describing each block by its own Cartesian tree, which removes the Euler tour and its factor 2. The sparse table is the simplest and, on the arrays that fit in a cache, often the fastest in practice.

The contracts [see File Contract.h]: a query asks for i <= j < n, and its answer is a leftmost minimum of the range (an audit, linear in the range); the items of a PlusMinusOneRangeMinimum differ by 1. The functions are defined in RangeMinimum.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapter 10

    1. Bender, M. Farach-Colton, The LCA problem revisited, Proceedings of the 4th Latin American Symposium on Theoretical Informatics (LATIN), LNCS 1776, 88-94, 2000, doi:10.1007/10719839_9

  1. Harel, R. E. Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing 13(2), 338-355, 1984, doi:10.1137/0213024

  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. Vuillemin, A unifying look at data structures, Communications of the ACM 23(4), 229-239, 1980, doi:10.1145/358841.358852

    1. Arlazarov, E. A. Dinic, M. A. Kronrod, I. A. Faradzev, On economical construction of the transitive closure of an oriented graph, Soviet Mathematics Doklady 11, 1209-1210, 1970 (the trick of the Four Russians)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes

Functions