Range Minimum Query

Range Minimum Queries ( RMQs ) address the problem to answer a request for the smallest element within a specified range of an array within the computer science. An efficient response has relevance for other problems of computer science, such as for text indexing and compression, flow graphs, etc.

• Lowest Common Ancestor 4.1
• 4.2 longest common prefix

Definition

Be an array of length with elements of a universe of total order, then deliver ( and with ) the position of the smallest element within the specified interval. Figure 1 illustrates the request on a sample sequence.

Trivial editing

There are two nontrivial solutions for problem solving, which are either space or time inefficient.

• Linear Scanning: By a linear scan of request time in worst-case and a space requirement of is achieved for each query.
• Precomputation of a lookup table: Naive is a precomputed table that stores the answers to all the possible range minimum queries. Thus, a constant request time is reached in, with combinations require space.

Suppose, however, that it is in a static array, and the inquiries are made on-line, making a clever precalculation and the construction of a suitable data structure can reduce the query time significantly. Here an almost constant request time is sought with linear space consumption.

Efficient construction

The pre- RMQ- Datenstukturen can be divided into two categories: ( a) array indexing, and ( b ) array encoding. In case ( a) the pre-calculated structure requires access to the array thereon RMQs answer. In case (b ) is accessed is not necessary to answer a RMQ. The solutions presented are assigned to the category of array indexing.

In the following step by step shows how the given problem can be reduced to a complexity of (linear space / precomputation time, request time constant ) by skillful pre-calculation.

Logarithmic space

In M. A. Bender et al. ( 2005), described a way to achieve. For this purpose, the results of all queries are precomputed broader length. Because of this, the actual RMQ is divided into a maximum of two equally long partial queries whose lengths are power of 2 and may overlap. Here, the maximum power of 2 is chosen, where is. Due to the pre-calculation, the result can be determined over the interval of in constant time. Figure 2 depicts the action and sets an example of how the RMQ (interval = red line) in two RMQs ( gray lines ) is broken. Be the table of precomputed answers. The algorithm includes three steps to determine the outcome of a RMQ:

At this point it is apparent that the specified solution is part of ( a) indexing the array, since the smaller of the two minima in the sub-requests must be determined and this two accesses need to be used.

Analysis

Due to the precalculation a RMQ can be answered. The additional data structure contains a maximum of precalculated minima for each position within the array because it is from the first array position to the end in the worst-case power of two. This reduces to the space requirement of. The precomputation required by dynamic programming, a runtime of steps, the following recurrence is solved: (see Figure 3) to calculate the corresponding table. The time required for the precomputation is.

Linear space

The solution presented is from Johannes Fischer and Heun ( 2011). Here, the space is reduced, wherein the input array is divided into blocks of length. O.B.d.A. be. Visually, the block formation is shown in Figure 4, which was exemplified divided here into four blocks. The RMQ can now max. three parts are broken down:

• A request that includes complete blocks ().
• Two questions, each relating to a portion of a block [ in block ] (,).

After processing the max. three sub-requests is obtained the respective minimum over the range spanned. In the last step, the actual values ​​are loaded from and compared. Thereupon, the position of the smallest of the max. three values ​​are output as a result. At this point it is apparent that the solution given category ( a) Array indexing is to be assigned.

Request on complete blocks

The RMQ, which terminates at block boundaries (ie complete blocks comprises ), can be answered in two by overlapping requests by the construction of Section 3.1. To store the minimum of each block in a list (Figure 4, is also. Thereafter, the known construction is used, resulting in a space of. Summary it can be said that in this case a RMQ can be computed in constant time, wherein the auxiliary data structure requires linear amount of space.

Requests to block parts

Each block is assigned a Cartesian tree. A Cartesian tree is constructed according to the following, recursive rules, and is exemplary shown in Figure 5.

Lemma: If the Cartesian trees of two arrays have the same structure, the following applies. The interested reader can read the proof of the lemma in John Fischer and Heun (2011, S.472 ).

Because of the lemma results in a reduction of in - block RMQs because not every block is pre-calculated individually, but suffice just the answers for all possible Cartesian trees above elements because each block can be in linear time ( Johannes Fischer and Heun 2011) on a Cartesian tree map, since the tree structure payback is. The number of trees equal to the Catalan number. The bit patterns of the trees serve as an index of the precomputed in - block table. A Cartesian tree is in this case uniquely represented by its level -order unary degree sequence ( LOUDS ), which is described by Jacobson (1989) and bits needed. Overall, this results in a space of.

As was shown, the problem can be reduced to linear space and constant query time by the original RMQ is divided into three parts inquiries. The minimum over completely encompassed blocks is calculated using the scheme of Section 3.1, for in - block queries blocks are mapped to Cartesian trees whose results completely precomputed no more than linearly with respect to the input need a lot of space.

Applications

In the following two use cases for RMQs are presented. Other applications include, for example, Johannes Fischer and Heun (2007, p.3) read.

Lowest Common Ancestor

An LCA request regarding a tree and two nodes provides either (or ) if it is on the path from the root to (respectively), or those nodes where the common path ends at and.

As described by Gabow, Bentley, and Tarjan (1984) first described, the LCA problem can be reduced linearly to the RMQ problem (and inverted, see Bender and Farach - Colton (2000)). This is of relevance, since thus LCA requests in constant time, and a linear space with respect to the input () can be solved, as is shown for example in J. Fischer and Heun (2007).

The reduction includes an Euler tour (or an in -order Baumtraversal ) in time over the LCA tree to map to an array, which is stored for each element in a corresponding Traversalnummer in by increments during the descent decremented (or during the ascent ) is, please refer to Figure 6, the array requires linear plenty of space because the number of edges of the original tree is limited by the node. For the array precalculation for RMQs above - described can now be performed. To solve the LCA problem now applies: where the position of the input node label inside.

Longest common prefix

In the text indexing RMQs can for finding LCP ( Longest Common Prefix ) are used in pattern search (or Longest Common suffix with RMQ on the inverted text ), the LCP a common prefix of the suffixes calculated that start in on position and.

To this end, the LCP - array of the suffix array is used and calculated to an inverse suffix array, which for th suffix in the suffix array returns its starting position in. On the basis of these two structures, the length of the LCP can now be computed in constant time using the following rule:.