Session 10C - Lower Bound for Succinct Range Minimum Query

The Range Minimum Query problem (RMQ) is a classical data structure problem in computer science. Given an integer array A[1..n], the 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]. The best known data structure uses 2n+n/(log n/ t)^t bits and answers queries in O(t) time, assuming the word-size is w=Θ(log n).

In this work, we prove the first lower bound for RMQ. Our lower bound shows that the state-of-the-art data structure is optimal in the regime of constant 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)} bits, in the cell-probe model with word-size w=Θ(log n).