Nearly Tight Lower Bounds for Succinct Range Minimum Query

Given an array of distinct integers $A[1\ldots n]$, the Range Minimum Query (RMQ) problem requires us to construct a data structure from $A$, supporting the RMQ query: given an interval $[a,b]\subseteq[1,n]$, return the index of the minimum element in subarray $A[a\ldots b]$, i.e. return $\text{argmin}_{i\in[a,b]}A[i]$. The fundamental problem has a long history. The textbook solution which uses $O(n)$ words of space and $O(1)$ time by Gabow, Bentley, Tarjan (STOC 1984) and Harel, Tarjan (SICOMP 1984) dates back to 1980s. The state-of-the-art solution is presented by Fischer, Heun (SICOMP 2011) and Navarro, Sadakane (TALG 2014). The solution uses $2n+n/\left(\frac{\log n}{t}\right)^t+\tilde{O}(n^{3/4})$ bits of space and $O(t)$ query time, assuming the word-size is $\Theta(\log n)$ bits. On the other hand, the only known lower bound is proven by Liu and Yu (STOC 2020). They show that any data structure which solves RMQ in $t$ query time must use $2n+n/(\log n)^{O(t^2\log^2t)}$ bits of space, assuming the word-size is $\Theta(\log n)$ bits. In this paper, we prove nearly tight lower bound for this problem. We show that, for any data structure which solves RMQ in $t$ query time, $2n+n/(\log n)^{O(t\log^2t)}$ bits of space is necessary in the cell-probe model with word-size $\Theta(\log n)$. We emphasize that, for any $r$, we present a lower bound of $t=\Omega(t_{opt}/\log^3 t_{opt})$, where $t_{opt}$ is the optimal time cost when the data structure is allowed to consume $2n+r$ bits of space. Hence our lower bound is nearly tight.