论文标题
下一个/上一个较大/较小的值查询的空间有效数据结构
Space-efficient Data Structure for Next/Previous Larger/Smaller Value Queries
论文作者
论文摘要
给定总订单中的大小$ n $的数组，我们考虑构建支持各种查询的数据结构的问题（范围最小/最大查询及其变体以及下一个/先前的较大/较小的查询）有效。在编码模型（即可以在没有输入数组的情况下可以回答查询）中，我们提出了$（3.701n + o（n））$ - 位数据结构，该结构支持$ O（\ log^{（\ ell）} n）$时间中的所有这些查询，对于任何积极的常量integer $ \ ell $ n log（$ n log），= n log n log n log^n log^^^（1） $ \ ell> 1 $，$ \ log^{（\ ell）} n = \ log（{\ log^{（\ ell-1）}} n）$）。我们的数据结构的空间与TSUR的当前最佳上限相匹配（Inf。Process。Lett。，2019），它不有效地支持查询。另外，我们表明至少$ 3.16n-θ（\ log n）$位对于回答所有查询是必需的。我们的结果是通过概括Gawrychowski和Nicholson的$（3n -θ（\ log n））$ - 位下限（ICALP，15）来回答尺寸$ n $的排列时的最小和最大查询。
Given an array of size $n$ from a total order, we consider the problem of constructing a data structure that supports various queries (range minimum/maximum queries with their variants and next/previous larger/smaller queries) efficiently. In the encoding model (i.e., the queries can be answered without the input array), we propose a $(3.701n + o(n))$-bit data structure, which supports all these queries in $O(\log^{(\ell)}n)$ time, for any positive constant integer $\ell$ (here, $\log^{(1)} n = \log n$, and for $\ell > 1$, $\log^{(\ell)} n = \log ({\log^{(\ell-1)}} n)$). The space of our data structure matches the current best upper bound of Tsur (Inf. Process. Lett., 2019), which does not support the queries efficiently. Also, we show that at least $3.16n-Θ(\log n)$ bits are necessary for answering all the queries. Our result is obtained by generalizing Gawrychowski and Nicholson's $(3n - Θ(\log n))$-bit lower bound (ICALP, 15) for answering range minimum and maximum queries on a permutation of size $n$.
