论文标题
简洁范围的下限最小查询
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\in [1,n]$, return the index $i\in[a,b]$ that minimizes $A[i]$, i.e., $ \ mathrm {argmin} _ {i \ in [a，b]} a [i] $。这个问题具有经典的解决方案，使用$ o（n）$空间和$ o（1）$查询时间，由Gabow，Bentley，Tarjan（Stoc，1984）和Harel，Tarjan（Sicomp，1984）。 Fischer，Heun（Sicomp，2011）和Navarro的最著名数据结构，Sadakane（Talg，2014年）使用$ 2N+N/（\ frac {\ frac {\ log n} {t} {t}）^t+\ t+\ tilde {o} {o}（o}（n^{3/4}） n）$。特别是，只要查询时间是常数，它使用$ 2N+N/\ MATHRM {poly} \ log n $ log n $位。 在本文中，我们证明了此问题的第一个下限，表明$ 2N+N/\ MATHRM {POLY} \ LOG N $空间对于恒定查询时间是必需的。通常，我们表明，如果数据结构具有查询时间$ o（t）$，则必须在单词大小的模型中使用至少$ 2N+n/（\ log n）^{\ tilde {o}（t^2）} $ space，带有单词size $ w =θ（\ log n）$。
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\in [1,n]$, return the index $i\in[a,b]$ that minimizes $A[i]$, i.e., $\mathrm{argmin}_{i\in[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/(\frac{\log n}{t})^t+\tilde{O}(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/\mathrm{poly}\log 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/\mathrm{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)^{\tilde{O}(t^2)}$ space, in the cell-probe model with word-size $w=Θ(\log n)$.
