Lower Bound for Succinct Range Minimum Query
share
Given an integer array A[1..n], the Range Minimum Query problem (RMQ) asks to preprocess A into a data structure, supporting RMQ queries: given a,b∈ [1,n], return the index i∈[a,b] that minimizes A[i], i.e., argmin_i∈[a,b] A[i]. This problem has a classic solution using O(n) space and O(1) query time by Gabow, Bentley, Tarjan (STOC, 1984) and Harel, Tarjan (SICOMP, 1984). The best known data structure by Fischer, Heun (SICOMP, 2011) and Navarro, Sadakane (TALG, 2014) uses 2n+n/(log n/t)^t+Õ(n^3/4) bits and answers queries in O(t) time, assuming the word-size is w=Θ(log n). In particular, it uses 2n+n/polylog n bits of space as long as the query time is a constant. In this paper, we prove the first lower bound for this problem, showing that 2n+n/polylog n space is necessary for constant query time. In general, we show that if the data structure has query time O(t), then it must use at least 2n+n/(log n)^Õ(t^2) space, in the cell-probe model with word-size w=Θ(log n).
READ FULL TEXT