Lower bound for succinct range minimum query

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., arg min i∈[a,b] A[i]. This problem has a classic solution using O(n) space and O(1) query time by Gabow, Bentley, Tarjan [GBT84] and Harel, Tarjan [HT84]. The best known data structure by Fischer, Heun [FH11] and Navarro, Sadakane [NS14] 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/poly log n bits of space when the query time is a constant. In this paper, we prove the first lower bound for this problem, showing that 2n+n/poly log 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).