Consider the following problem. Range Minimum Query, RMQ Given an array A[1..n] and a range [s,t] C [1,n], a range minimum query asks the position of the minimum value in A[s..t). If there exist more than one minimum values in the query range, return the leftmost one. We consider the indexing problem, that is, given the array A, we first construct a data structure D_a, then given a query range, we solve the problem using D_a- There exists a linear space (O(n) words) data structure for the RMQ problem supporting constant time queries [3, 4]. It is however complicated and there have been no efficient implementations until recently. In 2000, a simple solution [1] was given and after that, constant query time RMQ data structures are used in many algorithms. In this talk, we explain an O(n)-word data structure for the RMQ problem. Then we reduce the size of the data structure to just 2n + o(n) bits [2]. We also explain applications of the problem such as compressed suffix trees [5].
展开▼
机译：考虑以下问题。范围最小查询，RMQ给定阵列a [1..n]和范围[s，t] c [1，n]，范围最小查询询问[s..t）中的最小值的位置。如果查询范围中存在多个最小值，则返回最左侧的值。我们考虑索引问题，即给定阵列A，我们首先构建数据结构D_A，然后给出查询范围，我们使用D_A解决问题 - 存在线性空间（O（n）字）数据结构支持恒定时间查询的RMQ问题[3,4]。然而，它是复杂的，并且直到最近没有有效的实施。 2000年，给出了一个简单的解决方案[1]，之后，在许多算法中使用恒定查询时间RMQ数据结构。在此谈话中，我们解释了RMQ问题的O（n）-word数据结构。然后，我们将数据结构的大小降低到仅2N + O（n）位[2]。我们还解释了压缩后缀树等问题的应用[5]。
展开▼
