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 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-\Theta(\log n)$ bits are necessary for answering all the queries. Our result is obtained by generalizing Gawrychowski and Nicholson's $(3n - \Theta(\log n))$-bit lower bound (ICALP 15) for answering range minimum and maximum queries on a permutation of size $n$.

翻译：以总顺序为单位, 我们考虑构建一个数据结构的问题, 以便有效地支持各种查询( 以其变式和下一个/ 上一个/ 上一个/ 前较大/ 小的查询) 。 在编码模式( 即, 查询可以不使用输入数组回答) 中, 我们提议一个 $( 3. 701n + o( n) ) 美元- 比特数据结构, 支持所有这些查询 $( log ⁇ ( ell) 美元) 的时间, 对于任何正整数 $( $\ log ⁇ ( l) n) = n美元, 对于 $ > 1, $\ log {( ell) n = =\ log ( $\ =) n =\ log ( \ ll) = n$。 我们数据结构的空间与当前最高级 Tsur ( Inf. proc. plett., 2019) 支持不了有效查询。 另外, 我们显示至少3. 16n- Theta( log n n$) bits yless is supalal supalal leas mess a 15 a gsalalal lax lax legal