11institutetext: Chungnam National University, South Korea
11email<EMAIL_ADDRESS>Chungbuk National University, South
Korea
22email<EMAIL_ADDRESS>
# Space-efficient data structure for next/previous larger/smaller value
queries

Seungbum Jo 11 0000-0002-8644-3691 Geunho Kim 22 0000-0003-4705-0489

###### Abstract

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$.

###### Keywords:

Range minimum queries Encoding model Balanced parenthesis sequence.

##  1 Introduction

Given an array $A[1,\dots,n]$ of size $n$ from a total order and an interval
$[i,j]\subset[1,n]$, suppose there are $k$ distinct positions $i\leq p_{1}\leq
p_{2}\dots\leq p_{k}\leq j$ where $p_{1},p_{2},\dots,p_{k}$ are the positions
of minimum elements in $A[i,\dots,j]$. Then, for $q\geq 1$, range $q$-th
minimum query on the interval $[i,j]$ ($\textsf{RMin}{}(i,j,q)$) returns the
position $p_{q}$ (returns $p_{k}$ if $q>k$), and range minimum query on the
interval $[i,j]$ ($\textsf{RMin}{}(i,j)$) returns an arbitrary position among
$p_{1},p_{2},\dots,p_{k}$. One can also analogously define range $q$-th
maximum query (resp. range maximum query) on the interval $[i,j]$, denoted by
$\textsf{RMax}{}(i,j,q)$ (resp. $\textsf{RMax}{}(i,j)$).

In addition to the above queries, one can define next/previous larger/smaller
queries as follows. When the position $i$ is given, the previous smaller value
query on the position $i$ ($\textsf{PSV}{}(i)$) returns the rightmost position
$j<i$, where $A[j]$ is smaller than $A[i]$ (returns $0$ if no such $j$
exists), and the next smaller value query on the position $i$
($\textsf{NSV}{}(i)$) returns the leftmost position $j>i$ where $A[j]$ is
smaller than $A[i]$ (returns $n+1$ if no such $j$ exists). The previous (resp.
next) larger value query on the position $i$, denoted by $\textsf{PLV}{}(i)$
(resp. $\textsf{NLV}{}(i)$)) is also defined analogously.

In this paper, we focus on the problem of constructing a data structure that
efficiently answers all the above queries. We consider the problem in the
encoding model [15], which does not allow access to the input $A$ for
answering the queries after prepossessing. In the encoding data structure, the
lower bound of the space is referred to as the effective entropy of the
problem. Note that for many problems, their effective entropies have much
smaller size compared to the size of the inputs [15]. Also, an encoding data
structure is called succinct if its space usage matches the optimal up to
lower-order additive terms. The rest of the paper only considers encoding data
structures and assumes a $\Theta(\log n)$-bit word RAM model, where $n$ is the
input size.

###  1.0.1 Previous Work

The problem of constructing an encoding data structure for answering range
minimum queries has been well-studied because of its wide applications. It is
well-known that any two arrays have a different set of answers of range
minimum queries if and only if their corresponding Cartesian trees [19] are
distinct. Thus, the effective entropy of answering range minimum queries on
the array $A$ of size $n$ is $2n-\Theta(\log n)$ bits. Sadakane [17] proposed
the $(4n+o(n))$-bit encoding with $O(1)$ query time using the balanced-
parenthesis (BP) [11] of the Cartesian tree on $A$ with additional nodes.
Fisher and Heun [7] proposed the $(2n+o(n))$-bit data structure (hence,
succinct), which supports $O(1)$ query time using the depth-first unary degree
sequence (DFUDS) [2] of the 2d-min heap on $A$. Here, a 2d-min heap of $A$ is
an alternative representation of the Cartesian tree on $A$. By maintaining the
encodings of both 2d-min and max heaps on $A$ (2d-max heap can be defined
analogously to 2d-min heap), the encoding of [7] directly gives a
$(4n+o(n))$-bit encoding for answering both range minimum and maximum queries
in $O(1)$ time. Gawrychowski and Nicholson [8] reduced this space to
$(3n+o(n))$-bit while supporting the same query time for both queries. They
also showed that the effective entropy for answering the range minimum and
maximum queries is at least $3n-\Theta(\log n)$ bits.

Next/previous smaller value queries were motivated from the parallel computing
[3], and have application in constructing compressed suffix trees [14]. If all
elements in $A$ are distinct, one can answer both the next and previous
smaller queries using Fischer and Heun’s encoding for answering range minimum
queries [7]. For the general case, Ohlebusch et al. [14] proposed the
$(3n+o(n))$-bit encoding for supporting range minimum and next/previous
smaller value queries in $O(1)$ time. Fischer [6] improved the space to
$2.54n+o(n)$ bits while maintaining the same query time. More precisely, their
data structure uses the colored 2d-min heap on $A$, which is a 2d-min heap on
$A$ with the coloring on its nodes. Since the effective entropy of the colored
2d-min heap on $A$ is $2.54n-\Theta(\log n)$ bits [10], the encoding of [6] is
succinct. For any $q\geq 1$, the encoding of [6] also supports the range
$q$-th minimum queries in $O(1)$ time [9].

From the above, the encoding of Fischer [6] directly gives a
$(5.08n+o(n))$-bit data structure for answering the range $q$-th
minimum/maximum queries and next/previous larger/smaller value queries in
$O(1)$ time by maintaining the data structures of both colored 2d-min and max
heaps. Jo and Satti [9] improved the space to (i) $4n+o(n)$ bits if there are
no consecutive equal elements in $A$ and (ii) $4.585n+o(n)$ bits for the
general case while supporting all the queries in $O(1)$ time. They also showed
that if the query time is not of concern, the space of (ii) can be improved to
$4.088n+o(n)$ bits. Recently, Tsur [18] improved the space to $3.585n$ bits if
there are no consecutive equal elements in $A$ and $3.701n$ bits for the
general case. However, their encoding does not support the queries efficiently
($O(n)$ time for all queries).

###  1.0.2 Our Results

Given an array $A[1,\dots,n]$ of size $n$ with the interval
$[i,j]\subset[1,n]$ and the position $1\leq p\leq n$, we show the following
results:

  1. (a)

If $A$ has no two consecutive equal elements, there exists a
$(3.585n+o(n))$-bit data structure, which can answer (i)
$\textsf{RMin}{}(i,j)$, $\textsf{RMax}{}(i,j)$, $\textsf{PSV}{}(p)$, and
$\textsf{PLV}{}(p)$ queries in $O(1)$ time, and (ii) for any $q\geq 1$,
$\textsf{RMin}{}(i,j,q)$, $\textsf{RMax}{}(i,j,q)$, $\textsf{NSV}{}(p)$, and
$\textsf{NLV}{}(p)$ queries in $O(\log^{(\ell)}n)$ time111Throughout the
paper, we denote $\log n$ as the logarithm to the base $2$, for any positive
integer $\ell$.

  2. (b)

For the general case, the data structure of (a) uses $3.701n+o(n)$ bits while
supporting the same query time.

Our results match the current best upper bounds of Tsur [18] up to lower-order
additive terms while supporting the queries efficiently.

Table 1: Summary of the upper and lower bounds results of encoding data
structures for answering $q$-th minimum/maximum queries and next
larger/smaller value queries on the array $A[1,\dots,n]$, for any $q\geq 1$
(here, we can choose $\ell$ as any positive integer). Note that all our upper
bound results also support the range minimum/maximum and previous
larger/smaller value queries in $O(1)$ time (the data structures of [6, 9]
with $O(1)$ query time also support these queries in $O(1)$ time).

Array Type | Space (in bits) | Query time | Reference
---|---|---|---
Upper bounds
$A[i]\neq A[i+1]$ for all $i\in[1,n-1]$ | $4n+o(n)$ | $O(1)$ |  [9]
$3.585n$ | $O(n)$ |  [18]
$3.585n+o(n)$ | $O(\log^{(\ell)}n)$ | This paper
General array | $5.08n+o(n)$ | $O(1)$ |  [6, 9]
$4.088n+o(n)$ | $O(n)$ |  [9]
$4.585n+o(n)$ | $O(1)$
$3.701n$ | $O(n)$ |  [18]
$3.701n+o(n)$ | $O(\log^{(\ell)}n)$ | This paper
Lower bounds
Permutation | $3n-\Theta(\log n)$ |  |  [8]
General array | $3.16n-\Theta(\log n)$ |  | This paper

The main idea of our encoding data structure is to combine the BP of colored
2d-min and max heap of $A$. Note that all previous encodings in [8, 9, 18]
combine the DFUDS of the (colored) 2d-min and max heap on $A$. We first
consider the case when $A$ has no two consecutive elements (Section 3). In
this case, we show that by storing the BP of colored 2d-min heap on $A$ along
with its color information, there exists a data structure that uses at most
$3n+o(n)$ bits while supporting range minimum, range $q$-th minimum, and
next/previous smaller value queries efficiently. The data structure is
motivated by the data structure of Jo and Satti [9] which uses DFUDS of
colored 2d-min heap on $A$. Compared to the data structure of [9], our data
structure uses less space for the color information. Next, we show how to
combine the data structures on colored 2d-min and max heap on $A$ into a
single structure. The combined data structure is motivated by the idea of
Gawrychowski and Nicholson’s encoding [8] to combine the DFUDS of 2d-min and
max heap on $A$.

In Section 4, we consider the case that $A$ has consecutive equal elements. In
this case, we show that by using some additional auxiliary structures, the
queries on $A$ can be answered efficiently from the data structure on the
array $A^{\prime}$, which discards all the consecutive equal elements from
$A$.

Finally, in Section 5, we show that the effective entropy of the encoding to
support the range $q$-th minimum and maximum queries on $A$ is at least
$3.16n-\Theta(\log n)$ bits. Our result is obtained by extending the
$(3n-\Theta(\log n))$-bit lower bound of Gawrychowski and Nicholson [8] for
answering the range minimum and maximum queries on a permutation of size $n$.
We summarize our results in Table 1.

##  2 Preliminaries

This section introduces some data structures used in our results.

Figure 1: $\textsf{Min}{}(A)$ and $\textsf{Max}{}(A)$ on the array
$A=~{}5~{}4~{}5~{}3~{}1~{}2~{}6~{}3~{}1$.

###  2.0.1 2d min-heap and max-heap

Given an array $A[1,\dots,n]$ of size $n$, the 2d min-heap on $A$ (denoted by
$\textsf{Min}(A)$) [6] is a rooted and ordered tree with $n+1$ nodes, where
each node corresponds to the value in $A$, and the children are ordered from
left to right. More precisely, $\textsf{Min}(A)$ is defined as follows:

  1. 1.

The root of $\textsf{Min}(A)$ corresponds to $A[0]$ ($A[0]$ is defined as
$-\infty$).

  2. 2.

For any $i>0$, $A[i]$ corresponds to the $(i+1)$-th node of $\textsf{Min}(A)$
according to the preorder traversal.

  3. 3.

For any non-root node corresponds to $A[j]$, its parent node corresponds to
$A[\textsf{PSV}{}(j)]$.

In the rest of the paper, we refer to the node $i$ in $\textsf{Min}{}(A)$ as
the node corresponding to $A[i]$ (i.e., the $(i+1)$-th node according to the
preorder traversal). One can also define the 2d-max heap on $A$ (denoted as
$\textsf{Max}{}(A)$) analogously. More specifically, in $\textsf{Max}{}(A)$,
$A[0]$ is defined as $\infty$, and the parent of node $i>0$ corresponds to the
node $\textsf{PLV}{}(i)$ (see Figure 1 for an example). In the rest of the
paper, we only consider $\textsf{Min}{}(A)$ unless $\textsf{Max}{}(A)$ is
explicitly mentioned. The same definitions, and properties for
$\textsf{Min}{}(A)$ can be applied to $\textsf{Max}{}(A)$.

For any $i>0$, $\textsf{Min}{}(A)$ is the relevant tree of the node $i$ if the
node $i$ is an internal node in $\textsf{Min}{}(A)$. From the definition of
$\textsf{Min}{}(A)$, Tsur [18] showed the following lemma.

######  Lemma 1 ([18]).

For any $i\in\\{1,2,\dots,n-1\\}$, the following holds:

  1. (a)

If $\textsf{Min}{}(A)$ is a relevant tree of the node $i$, then the node
$(i+1)$ is the leftmost child of the node $i$ in $\textsf{Min}{}(A)$.

  2. (b)

If $A$ has no two consecutive equal elements, $\textsf{Min}{}(A)$ (resp.
$\textsf{Max}{}(A)$) is a relevant tree of the node $i$ if and only if the
node $i$ is a leaf node in $\textsf{Max}{}(A)$ (resp. $\textsf{Min}{}(A)$).

Figure 2: $\textsf{cMin}{}(A)$ and $\textsf{cMax}{}(A)$ on the array
$A=~{}5~{}4~{}5~{}3~{}1~{}2~{}6~{}3~{}1$. The nodes with slash line indicate
the valid nodes.

###  2.0.2 Colored 2d min-heap and max-heap

The colored 2d-min heap of $A$ (denoted by $\textsf{cMin}{}(A)$) [6] is
$\textsf{Min}{}(A)$ where each node is colored red or blue as follows. The
node $i$ in $\textsf{cMin}{}(A)$ is colored red if and only if $i$ is not the
leftmost child of its parent node, and $A[i]\neq A[j]$, where the node $j$ is
the node $i$’s immediate left sibling. Otherwise, the node $i$ is colored
blue. One can also define the colored 2d-max heap on $A$ (denoted by
$\textsf{cMax}{}(A)$) analogously (see Figure 2 for an example). The following
lemma says that we can obtain the color of some nodes in $\textsf{cMin}{}(A)$
from their tree structures.

######  Lemma 2.

For any node $i$ in $\textsf{cMin}{}(A)$, the following holds:

  1. (a)

If the node $i$ is the leftmost child of its parent node, the color of the
node $i$ is always blue.

  2. (b)

If $A$ has no two consecutive equal elements, the color of the node $i$ is
always red if its immediate left sibling is a leaf node.

###### Proof.

(a) is directly proved from the definition of $\textsf{cMin}{}(A)$. Also, if
the immediate left sibling $j$ of the node $i$ is a leaf node, $j$ is equal to
$i-1$ (note that the preorder traversal of $\textsf{cMin}{}(A)$ visits the
node $i$ immediately after visiting the node $j$). Thus, if $A$ has no
consecutive equal elements, the color of the node $i$ is red.

We say the node $i$ in $\textsf{cMin}{}(A)$ is valid if the node $i$ is a non-
root node in $\textsf{cMin}{}(A)$ which is neither the leftmost child nor the
immediate right sibling of any leaf node. Otherwise, the node $i$ is invalid.
By Lemma 2, if $A$ has no two consecutive equal elements, the color of the
invalid nodes of $\textsf{cMin}{}(A)$ can be decoded from the tree structure.

###  2.0.3 Rank and Select queries on bit arrays

Given a bit array $B[1,\dots,n]$ of size $n$, and a pattern
$p\in\\{0,1\\}^{+}$, (i) $\textsf{rank}{}_{p}(i,B)$ returns the number of
occurrence of the pattern $p$ in $B[1,\dots,i]$, and (ii)
$\textsf{select}{}_{p}(j,B)$ returns the first position of the $j$-th
occurrence of the pattern $p$ in $B$. The following lemma shows that there
exists a succinct encoding, which supports both rank and select queries on $B$
efficiently.

######  Lemma 3 ([12, 16]).

Given a bit array $B[1,\dots,n]$ of size $n$ containing $m$ $1$s, and a
pattern $p\in\\{0,1\\}^{+}$ with $|p|\leq\frac{\log n}{2}$, the following
holds:

  * •

There exists a $(\log{n\choose m}+o(n))$-bit data structure for answering both
$\textsf{rank}{}_{p}(i,B)$ and $\textsf{select}{}_{p}(j,B)$ queries in $O(1)$
time. Furthermore, the data structure can access any $\Theta(\log n)$-sized
consecutive bits of $B$ in $O(1)$ time.

  * •

If one can access any $\Theta(\log n)$-sized consecutive bits of $B$ in $O(1)$
time, both $\textsf{rank}{}_{p}(i,B)$ and $\textsf{select}{}_{p}(j,B)$ queries
can be answered in $O(1)$ time using $o(n)$-bit auxiliary structures.

###  2.0.4 Balanced-parenthesis of trees

Given a rooted and ordered tree $T$ with $n$ nodes, the balanced-parenthesis
(BP) of $T$ (denoted by $\textsf{BP}(T)$) [11] is a bit array defined as
follows. We perform a preorder traversal of $T$. We then add a $0$ to
$\textsf{BP}(T)$ when we first visit a node and add a $1$ to $\textsf{BP}(T)$
after visiting all nodes in the subtree of the node. Since we add single $0$
and $1$ to $\textsf{BP}(T)$ per each node in $T$, the size of
$\textsf{BP}{}(T)$ is $2n$. For any node $i$ in $T$, we define $f(i,T)$ and
$s(i,T)$ as the positions of the $0$ and $1$ in $\textsf{BP}{}(T)$ which are
added when the node $i$ is visited, respectively. When $T$ is clear from the
context, we write $f(i)$ (resp. $s(i)$) to denote $f(i,T)$ (resp. $s(i,T)$).
If $T$ is a 2d-min heap, $f(i,T)=\textsf{select}{}_{0}(i+1,BP(T))$ by the
definition of 2d-min heap.

##  3 Data structure on arrays with no consecutive equal elements

In this section, for any positive integer $\ell$, we present a
$(3.585n+o(n))$-bit data structure on $A[1,\dots,n]$, which supports (i) range
minimum/maximum and previous larger/smaller queries on $A$ in $O(1)$ time, and
(ii) range $q$-th minimum/maximum and next larger/smaller value queries on $A$
in $O(\log^{(\ell)}n)$ time for any $q\geq 1$, when there are no two
consecutive equal elements in $A$. We first describe the data structure on
$\textsf{cMin}{}(A)$ for answering the range minimum, range $q$-th minimum,
and next/previous smaller value queries on $A$. Next, we show how to combine
the data structures on $\textsf{cMin}{}(A)$ and $\textsf{cMax}{}(A)$ in a
single structure.

###  3.0.1 Encoding data structure on $\textsf{cMin}{}(A)$

We store $\textsf{cMin}{}(A)$ by storing its tree structure along with the
color information of the nodes. To store the tree structure, we use
$\textsf{BP}(\textsf{cMin}{}(A))$. Also, for storing the color information of
the nodes, we use a bit array $c_{min}$, which stores the color of all valid
nodes in $\textsf{cMin}{}(A)$ according to the preorder traversal order. In
$c_{min}$ we use $0$ (resp. $1$) to indicate the color blue (resp. red). It is
clear that $\textsf{cMin}{}(A)$ can be reconstructed from
$\textsf{BP}{}(\textsf{cMin}{}(A))$ and $c_{min}$. Since
$\textsf{BP}{}(\textsf{cMin}{}(A))$ and $c_{min}$ takes $2(n+1)$ bits and at
most $n$ bits, respectively, the total space for storing $\textsf{cMin}{}(A)$
takes at most $3n+2$ bits. Note that a similar idea is used in Jo and Satti’s
extended DFUDS [9], which uses the DFUDS of $\textsf{cMin}{}(A)$ for storing
the tree structure. However, extended DFUDS stores the color of all nodes
other than the leftmost children, whereas $c_{min}$ does not store the color
of all invalid nodes. The following lemma shows that from
$\textsf{BP}{}(\textsf{cMin}{}(A))$, we can check whether the node $i$ is
valid or not without decoding the entire tree structure.

######  Lemma 4.

The node $i$ is valid in $\textsf{cMin}{}(A)$ if and only if $f(i)>2$ and both
$BP(\textsf{cMin}{}(A))[f(i)-2]$ and $BP(\textsf{cMin}{}(A))[f(i)-1]$ are $1$.

###### Proof.

If both $BP(\textsf{cMin}{}(A))[f(i)-2]$ and $BP(\textsf{cMin}{}(A))[f(i)-1]$
are $1$, the preorder traversal of $\textsf{cMin}{}(A)$ must complete the
traversal of two subtrees consecutively just before visiting the node $i$ for
the first time, which implies the node $i$’s immediate left sibling is not a
leaf node (hence the node $i$ is valid).

Conversely, if $BP(\textsf{cMin}{}(A))[f(i)-1]=0$, $\textsf{cMin}{}(A)$ is a
relevant tree of the node $i-1$. Thus, the node $i$ is the leftmost child of
the node $(i-1)$ by Lemma 1. Next, if $BP(\textsf{cMin}{}(A))[f(i)-2]=0$ and
$BP(\textsf{cMin}{}(A))[f(i)-1]=1$, the node $(i-1)$ is the immediate left
sibling of the node $i$ since $f(i)-2$ is equal to $f(i-1)$. Also the node
$(i-1)$ is a leaf node since $f(i)-1$ is equal to $s(i-1)$. Thus, the node $i$
is invalid in this case.

Now we describe how to support range minimum, range $q$-th minimum, and
next/previous smaller value queries efficiently on $A$ using
$\textsf{BP}{}(\textsf{cMin}{}(A))$ and $c_{min}$ with $o(n)$-bit additional
auxiliary structures. Note that both the range minimum and previous smaller
value query on $A$ can be answered in $O(1)$ time using
$BP(\textsf{cMin}{}(A))$ with $o(n)$-bit auxiliary structures [13, 5]. Thus,
it is enough to consider how to support a range $q$-th minimum and next
smaller value queries on $A$. We introduce the following lemma of Jo and Satti
[9], which shows that one can answer both queries with some navigational and
color queries on $\textsf{cMin}{}(A)$.

######  Lemma 5 ([9]).

Given $\textsf{cMin}{}(A)$, suppose there exists a data structure, which can
answer (i) the tree navigational queries (next/previous sibling, subtree size,
degree, level ancestor, child rank, child select, and parent222refer to Table
1 in [13] for detailed definitions of the queries) on $\textsf{cMin}{}(A)$ in
$t(n)$ time, and the following color queries in $s(n)$ time:

  * •

$\textsf{color}{}(i)$: return the color of the node $i$

  * •

$\textsf{PRS}{}(i)$: return the rightmost red sibling to the left of the node
$i$.

  * •

$\textsf{NRS}{}(i)$: return the leftmost red sibling to the right of the node
$i$.

Then for any $q\geq 1$, range $q$-th minimum, and the next smaller value
queries on $A$ can be answered in $O(t(n)+s(n))$ time.

Since all tree navigational queries in Lemma 5 can be answered in $O(1)$ time
using $\textsf{BP}{}(\textsf{cMin}{}(A))$ with $o(n)$-bit auxiliary structures
[13], it is sufficient to show how to support $\textsf{color}{}(i)$,
$\textsf{PRS}{}(i)$, and $\textsf{NRS}{}(i)$ queries using
$\textsf{BP}{}(\textsf{cMin}{}(A))$ and $c_{min}$. By Lemma 3 and 4, we can
compute $\textsf{color}{}(i)$ in $O(1)$ time using $o(n)$-bit auxiliary
structures by the following procedure: We first check whether the node $i$ is
valid using $O(1)$ time by checking the values at the positions $f(i)-1$ and
$f(i)-2$ in $\textsf{BP}{}(\textsf{cMin}{}(A))$. If the node $i$ is valid
(i.e., both the values are $1$), we answer $\textsf{color}{}(i)$ in $O(1)$
time by returning $c_{min}[j]$ where $j$ is
$\textsf{rank}{}_{110}(f(i),\textsf{BP}(\textsf{cMin}{}(A)))$ (otherwise, by
Lemma 4, we answer $\textsf{color}{}(i)$ as blue if and only if the node $i$
is the leftmost child of its parent node). Next, for answering
$\textsf{PRS}{}(i)$ and $\textsf{NRS}{}(i)$, we construct the following
$\ell^{\prime}$-level structure ($\ell^{\prime}$ will be decided later):

  * •

At the first level, we mark every $(\log n\log\log n)$-th child node and
maintain a bit array $M_{1}[1,\dots,n]$ where $M_{1}[t]=1$ if and only if the
node $t$ is marked (recall that the node $t$ is the node in
$\textsf{Min}{}(A)$ whose preorder number is $t$). Since there are $n/(\log
n\log\log n)=o(n)$ marked nodes, we can store $M_{1}$ using $o(n)$ bits while
supporting rank queries in $O(1)$ time by Lemma 3 (in the rest of the paper,
we ignore all floors and ceilings, which do not affect to the results). Also
we maintain an array $P_{1}$ of size $n/(\log n\log\log n)$ where $P_{1}[j]$
stores both $\textsf{PRS}{}(s)$ and $\textsf{NRS}{}(s)$ if $s$ is the $j$-th
marked node according to the preorder traversal order. We can store $P_{1}$
using $O(n\log n/(\log n\log\log n))=o(n)$ bits.

  * •

For the $i$-th level where $1<i\leq\ell^{\prime}$, we mark every
$(\log^{(i)}n\log^{(i+1)}n)$-th child node. We then maintain a bit array
$M_{i}$ which is defined analogously to $M_{1}$. We can store $M_{i}$ using
$o(n)$ bits by Lemma 3.

Now for any node $p$, let $cr(p)$ be the child rank of $p$, i.e., the number
of left siblings of $p$. Also, let $pre_{(i-1)}(p)$ (resp. $next_{(i-1)}(p)$)
be the rightmost sibling of $p$ to the left (resp. leftmost sibling of $p$ to
the right) which is marked at the $(i-1)$-th level. Suppose $s$ is the $j$-th
marked node at the current level according to the preorder traversal order.
Then we define an array $P_{i}$ of size $n/(\log^{(i)}n\log^{(i+1)}n)$ as
$P_{i}[j]$ stores both (i) the smaller value between
$cr(s)-cr(\textsf{PRS}{}(s))$ and $cr(s)-cr(pre_{(i-1)}(s))$, and (ii) the
smaller value between $cr(\textsf{NRS}{}(s))-cr(s)$ and
$cr(next_{(i-1)}(s))-cr(s)$. Since both (i) and (ii) are at most
$\log^{(i-1)}n\log^{(i)}n$, we can store $P_{i}$ using
$O(n\log^{(i)}n/(\log^{(i)}n\log^{(i+1)}n))=o(n)$ bits. Therefore, the overall
space is $O(n/\log^{(\ell^{\prime}+1)}n)=o(n)$ bits in total for any positive
integer $\ell^{\prime}$.

To answer $\textsf{PRS}{}(i)$ (the procedure for answering $\textsf{NRS}{}(i)$
is analogous), we first scan the left siblings of $i$ using the previous
sibling operation. Whenever the node $i_{1}$ is visited during the scan, we
check whether (i) $\textsf{color}{}(i_{1})=red$, or (ii)
$M_{\ell^{\prime}}[i_{1}]=1$ in $O(1)$ time. If $i_{1}$ is neither the case
(i) nor (ii), we continue the scan. If $i_{1}$ is in the case (i), we return
$i_{1}$ as the answer. If $i_{1}$ is in the case (ii), we jump to the
$i_{1}$’s left sibling $i_{2}$ whose child rank is
$cr(i_{1})-P_{\ell^{\prime}}[j]$, where
$j=\textsf{rank}{}_{1}(i_{1},M_{\ell^{\prime}-1})$. Since the node $i_{2}$
always satisfies one of the following: $\textsf{color}{}(i_{2})=red$ or
$M_{\ell^{\prime}-1}[i_{2}]=1$, we can answer $\textsf{PRS}{}(i)$ by
iteratively performing child rank and rank operations at most
$O(\ell^{\prime})$ times after finding $i_{2}$. Thus, we can answer
$\textsf{PRS}{}(i)$ in $O(\ell^{\prime})$ time in total (we scan at most
$O(\ell^{\prime})$ nodes to find $i_{2}$). By choosing $\ell$ as
$\ell^{\prime}+2$, we obtain the following theorem.

######  Theorem 3.1.

Given an array $A[1,\dots,n]$ of size $n$ and any positive integer $\ell$, we
can answer (i) range minimum and previous smaller value queries in $O(1)$
time, and (ii) range $q$-th minimum and next smaller value queries for any
$q\geq 1$ in $O(\log^{(\ell)}n)$ time, using
$\textsf{BP}{}(\textsf{cMin}{}(A))$ and $c_{min}$ with $o(n)$-bit auxiliary
structures.

Theorem 3.1 implies that there exists a data structure of $\textsf{cMax}{}(A)$
(composed to $\textsf{BP}(\textsf{cMax}{}(A))$ and $c_{max}$ with $o(n)$-bit
auxiliary structures), which can answer (i) range maximum and previous larger
value queries in $O(1)$ time, and (ii) range $q$-th maximum and next larger
value queries for any $q\geq 1$ in $O(\log^{(\ell)}n)$ time.

###  3.0.2 Combining the encoding data structures on $\textsf{cMin}{}(A)$ and
$\textsf{cMax}{}(A)$

We describe how to combine the data structure of Theorem 3.1 on
$\textsf{cMin}{}(A)$ and $\textsf{cMax}{}(A)$ using $3.585n+o(n)$ bits in
total. We first briefly introduce the idea of Gawrychowski and Nicholson [8]
to combine the DFUDS of $\textsf{Min}{}(A)$ and $\textsf{Max}{}(A)$. In DFUDS,
any non-root node $i$ is represented as a bit array $0^{d_{i}}1$ where $d_{i}$
is the degree of $i$ [2]. The encoding of [8] is composed of (i) a bit array
$U[1,\dots,n]$, where $U[i]$ indicates the relevant tree of the node $i$, and
(ii) a bit array $S=s_{1}s_{2}\dots s_{n}$ where $s_{i}$ is the bit array,
which omits the first $0$ from the DFUDS of the node $i$ on its relevant tree.
To decode the DFUDS of the node $i$ in $\textsf{Min}{}(A)$ or
$\textsf{Max}{}(A)$, first check whether the tree is the relevant tree of the
node $i$ by referring to $U[i]$. If so, one can decode it by prepending $0$ to
$s_{i}$. Otherwise, the decoded sequence is simply $1$ by Lemma 1(b). Also,
Gawrychowski and Nicholson [8] showed that $U$ and $S$ take at most $3n$ bits
in total. The following lemma shows that a similar idea can also be applied to
combine $\textsf{BP}{}(\textsf{cMin}{}(A))$ and
$\textsf{BP}{}(\textsf{cMax}{}(A))$ (the lemma can be proved directly from
Lemma 1).

######  Lemma 6.

For any node $i\in\\{1,2,\dots,n-1\\}$, if $\textsf{cMin}{}(A)$ is a relevant
tree of the node $i$, $f(i+1,\textsf{cMin}{}(A))=f(i,\textsf{cMin}{}(A))+1$,
and $f(i+1,\textsf{cMax}{}(A))=f(i,\textsf{cMax}{}(A))+k$, for some $k>1$.
Otherwise, $f(i+1,\textsf{cMax}{}(A))=f(i,\textsf{cMax}{}(A))+1$, and
$f(i+1,\textsf{cMin}{}(A))=f(i,\textsf{cMin}{}(A))+k$, for some $k>1$.

Figure 3: Combined data structure of $\textsf{cMin}{}(A)$ and
$\textsf{cMax}{}(A)$. $i$-th column of the table shows (i) the substring of
$\textsf{BP}{}(\textsf{cMin}{}(A))$ and $\textsf{BP}{}(\textsf{cMax}{}(A))$
begin at position $f(i-1)+1$ and end at position $f(i)$ (shown in the second
and the third row, respectively), and (ii) $s_{i}$ for each $i$ (shown in the
fourth row).

We now describe our combined data structure of $\textsf{cMin}{}(A)$ and
$\textsf{cMax}{}(A)$. We first maintain the following structures to store
$\textsf{BP}{}(\textsf{cMin}{}(A))$ and $\textsf{BP}{}(\textsf{cMax}{}(A))$:

  1. 1.

The same bit array $U[1,\dots,n-1]$ as in the encoding of [8]. We define
$U[i]=0$ (resp. $U[i]=1$) if $\textsf{cMin}{}(A)$ (resp. $\textsf{cMax}{}(A)$)
is a relevant tree of the node $i$. For example, $U[6]=0$ since
$\textsf{cMin}{}(A)$ is a relevant tree of the node $6$.

  2. 2.

For each node $i\in\\{1,2,\dots,n-1\\}$, suppose the tree
$T\in\\{\textsf{cMin}{}(A),\textsf{cMax}{}(A)\\}$ is not a relevant tree of
$i$, and let $k_{i}$ be the number of ones between $f(i,T)$ and $f(i+1,T)$.
Now let $S=s_{1}s_{2}\dots s_{n-1}$ be a bit array, where $s_{i}$ is defined
as $1^{k_{i}-1}0$. For example, since there exist three $1$’s between $f(6)$
and $f(7)$ in $\textsf{cMax}{}(A)$, $s_{6}=110$. Then, $S$ is well-defined by
Lemma 6 ($k_{i}\geq 1$ for all $i$). Also, since there are at most $n-1$ ones
and exactly $n-1$ zeros by lemma 1(b), the size of $S$ is at most $2(n-1)$. We
maintain $S$ using the following two arrays:

    1. (a)

An array $D[1,\dots n-1]$ of size $n$ where $D[i]=0$ if $s_{i}$ contains no
ones, $D[i]=1$ if $s_{i}$ contains a single one, and $D[i]=2$ otherwise. For
example, $D[6]=2$, since $s_{6}$ has two ones. We maintain $D$ using the data
structure of Dodis et al. [4], which can decode any $\Theta(\log n)$
consecutive elements of $D$ in $O(1)$ time using $\left\lceil(n-1)\log
3\right\rceil$ bits. Now let $k$ and $\ell$ be the number of $1$’s and $2$’s
in $D$, respectively.

    2. (b)

Let $i_{2}$ be the position of the $i$-th $2$ in $D$. Then, we store a bit
array $E=e_{1}e_{2},\dots,e_{\ell}$ where $e_{i}$ is a bit array defined by
omitting the first two $1$’s from $s_{i_{2}}$. For example, since the $6$ is
the first position of $D$ whose value is $2$ and $s_{6}=110$, $e_{1}$ is
defined as $0$. The size of $E$ is at most $2(n-1)-(n-1)-(k+\ell)=n-k-\ell$.

  3. 3.

We store both $f(n,\textsf{cMin}{}(A))$, and $f(n,\textsf{cMax}{}(A))$ using
$O(\log n)$ bits.

To store both $c_{min}$ and $c_{max}$, we simply concatenate them into a
single array $c_{minmax}$, and store the length of $c_{min}$ using $O(\log n)$
bits. Then, by Lemma 4, the size of $c_{minmax}$ is $k+\ell$. Thus, our
encoding of $\textsf{cMin}{}(A)$ and $\textsf{cMax}{}(A)$ takes at most
$(n-1)+(n-1)\log 3+(n-k-\ell)+(k+\ell)+O(\log n)=(2+\log 3)n+O(\log
n)<3.585n+O(\log n)$ bits in total [18]. An overall example of our encoding is
shown in Figure 3. Now we prove the main theorem in this section.

######  Theorem 3.2.

Given an array $A[1,\dots,n]$ of size $n$ and any positive integer $\ell$,
suppose $A$ has no two consecutive equal elements. Then there exists a
$(3.585n+o(n))$-bit encoding data structure which can answer (i) range
minimum/maximum and previous larger/smaller value queries in $O(1)$ time, and
(ii) range $q$-th minimum/maximum and next larger/smaller value queries in
$O(\log^{(\ell)}n)$ time, for any $q\geq 1$.

###### Proof.

We show how to decode any $\log n$ consecutive bits of
$\textsf{BP}(\textsf{cMin}{}(A))$, which proves the theorem. Note that the
auxiliary structures and the procedure for decoding
$\textsf{BP}(\textsf{cMax}{}(A))$ are analogous. Let $B[1,\dots,f(n)-1]$ be a
subarray of $\textsf{BP}(\textsf{cMin}{}(A))$ of size $f(n)-1$, which is
defined as $\textsf{BP}(\textsf{cMin}{}(A))[2,\dots,f(n)]$. Then it is enough
to show how to decode $\log n$ consecutive bits of $B$ in $O(1)$ time using
$o(n)$-bit auxiliary structures (note that $\textsf{BP}(\textsf{cMin}{}(A))$
is $0\cdot B\cdot 1^{2n+2-f(n)}$). We also denote $f(n)-1$ by $f^{\prime}(n)$
in this proof.

We first define correspondences between the positions of $B$ and $D$, and
between the positions of $B$ and $E$ as follows. For each position
$j\in\\{1,\dots,f^{\prime}(n)\\}$ of $B$, let $\alpha(j)$ and $\beta(j)$ be
the corresponding positions of $j$ in $D$ and $E$, respectively. We define
both $\alpha(1)$ and $\beta(1)$ as $1$, and for each
$j\in\\{2,\dots,f^{\prime}(n)\\}$, we define $\alpha(j)$ as
$\textsf{rank}{}_{0}(j-1,B)$. Next, let $k$ be the number of $2$’s in
$D[1,\dots,\alpha(j)]$ and $j^{\prime}$ be the number of $1$’s in $B$ between
$B[j]$ and the and the leftmost $0$ in $B[j,\dots,f(\alpha(j+1))]$. Then
$\beta(j)$ is defined as (i) $1$ if $k=0$, (ii) $\textsf{select}{}_{0}(k,E)+1$
if $k>0$ and $D[\alpha(j)]\neq 2$, and (iii)
$\textsf{select}{}_{0}(k,E)-\max{}(j^{\prime}-3,0)$ otherwise. Then any
subarray of $B$ starting from the position $j$ can be constructed from the
subarrays of $U$, $D$ and $E$ starting from the positions
$\textsf{rank}{}_{0}(j,B)$, $\alpha(j)$ and $\beta(j)$, respectively.

Now, for $i\in\\{1,2,\dots,\left\lceil(f^{\prime}(n))/\log n\right\rceil\\}$,
let the $i$-th block of $B$ be $B[\left\lceil(i-1)\log
n+1\right\rceil,\dots,\min{}(\left\lceil i\log n\right\rceil,f^{\prime}(n))]$.
Then, it is enough to decode at most two consecutive blocks of $B$ to
construct any $\log n$ consecutive bits of $B$. Next, we define the $i$-th
block of $U$, $D$, and $E$ as follows:

  * •

$i$-th block of $U$ is defined as a subarray of $U$ whose starting and ending
positions are $\textsf{rank}{}_{0}(\left\lceil(i-1)\log n\right\rceil,B)$, and
$\textsf{rank}{}_{0}(\min{}(\left\lceil i\log
n\right\rceil-1,f^{\prime}(n)),B)$, respectively. To decode the blocks of $U$
without $B$, we mark all the starting positions of the blocks of $U$ using a
bit array $U_{1}$ of size $f^{\prime}(n)$ where $U_{1}[i]=1$ if and only if
the position $i$ is the starting position of the block in $U$. Then, since
$U_{1}$ contains at most $O(f^{\prime}(n)/\log n)=o(n)$ $1$’s, we can store
$U_{1}$ using $o(n)$ bits while supporting rank and select queries in $O(1)$
time by Lemma 3.

  * •

$i$-th block of $D$ is defined as a subarray of $D$ whose starting and ending
positions are $\alpha(\left\lceil(i-1)\log n\right\rceil+1)$ and
$\alpha(\min{}(\left\lceil i\log n\right\rceil,f^{\prime}(n)))$, respectively.
Then, the size of each block of $D$ is at most $\log n$, since any position of
$D$ has at least one corresponding position in $B$. We maintain a bit array
$D_{1}$ analogous to $U_{1}$ using $o(n)$ bits. Also, to indicate the case
that two distinct blocks of $D$ share the same starting position, we define
another bit array $D_{2}$ of size $\left\lceil f^{\prime}(n)/\log
n\right\rceil$ where $D_{2}[i]=1$ if and only if $i$-th block of $D$ has the
same starting position as the $(i-1)$-th block of $D$. We store $D_{2}$ using
the data structure of Lemma 3 using $o(n)$ bits to rank and select queries in
$O(1)$ time. Then, we can decode any block of $D$ in $O(1)$ time using rank
and select operations on $D_{1}$ and $D_{2}$.

  * •

$i$-th block of $E$ is defined as a subarray of $E$ whose starting and ending
positions are $\beta(\left\lceil(i-1)\log n\right\rceil+1)$ and
$\beta(\min{}(\left\lceil i\log n\right\rceil,f^{\prime}(n)))$, respectively.
To decode the blocks of $E$, we maintain two bit arrays $E_{1}$ and $E_{2}$
analogous to $D_{1}$ and $D_{2}$, respectively, using $o(n)$ bits.

Note that, unlike $D$, the size of some blocks in $E$ can be arbitrarily large
since some positions in $E$ do not have the corresponding positions in $B$. To
handle this case, we classify each block of $E$ as bad block and good block
where the size of bad block is at least at $c\log n$ for some constant $c\geq
9$, whereas the size of good block is less than $c\log n$. If the $i$-th block
of $E$ is good (resp. bad), we say it as $i$-th good (resp. bad) block.

For each $i$-th bad block of $E$, let $F_{i}$ be a subsequence of the $i$-th
bad block, which consists of all bits at the position $j$ where
$\beta^{-1}(j)$ exists. We store $F_{i}$ explicitly, which takes $\Theta(n)$
bits in total (the size of $F_{i}$ is at most $\log n$). However, we can apply
the same argument used in [8] to maintain min-bad block due to the fact that
each position in $E$ corresponds to at least one position in either
$\textsf{BP}{}(\textsf{cMin}{}(A))$ or $\textsf{BP}{}(\textsf{cMax}{}(A))$.
The argument says that for each $i$-th bad block of $E$, one can save at least
$\log n$ bits by maintaining it in a compressed form. Thus, we can maintain
$F_{i}$ for all $i$-th bad blocks of $E$ without increasing the total space.

Next, let $g(u,d,e,b)$ be a function, which returns a subarray of $B$ from the
subarrays of $U$, and $D$, and $E$ as follows (suppose $u=u[1]\cdot
u^{\prime}$ and $d=d[1]\cdot d^{\prime}$):

$g(u,d,e,b)=\begin{cases}\epsilon&\text{if}~{}u=\epsilon~{}\text{or}~{}d=\epsilon\\\
0\cdot g(u^{\prime},d^{\prime},e,b)&\text{if}~{}u[1]\neq
b~{}\text{and}~{}d[1]\neq 2\\\ 0\cdot
g(u^{\prime},d^{\prime},e^{\prime},b)&\text{if}~{}u[1]\neq
b,~{}d[1]=2,~{}\text{and}~{}e=1^{t}0\cdot e^{\prime}\\\ 10\cdot
g(u^{\prime},d^{\prime},e,b)&\text{if}~{}u[1]=b~{}\text{and}~{}d[1]=0\\\
110\cdot
g(u^{\prime},d^{\prime},e,b)&\text{if}~{}u[1]=b~{}\text{and}~{}d[1]=1\\\
1^{t}\cdot
g(u,d,e^{\prime},b)&\text{if}~{}u[1]=b,~{}d[1]=2,~{}\text{and}~{}e=1^{t}\cdot
e^{\prime}\\\ 1^{t+3}0\cdot
g(u^{\prime},d^{\prime},e^{\prime},b)&\text{if}~{}u[1]=b,~{}d[1]=2,~{}\text{and}~{}e=1^{t}0\cdot
e^{\prime}\\\ \end{cases}$

We store a precomputed table that stores $g(u,d,e,b)$ for all possible $u$,
$d$, and $e$ of sizes $\frac{1}{4}\log n$ and $b\in\\{0,1\\}$ using
$O(2^{\frac{1}{4}\log n+\frac{3}{2}\cdot\frac{1}{4}\log n+\frac{1}{4}\log
n}\log n)=O(n^{\frac{7}{8}}\log n)=o(n)$ bits.

To decode the $i$-th block of $B$, we first decode the $i$-block of $U$ and
$D$ in $O(1)$ time using rank and select queries on $U_{1}$, $D_{1}$, and
$D_{2}$. Let these subarrays be $b_{u}$ and $b_{d}$, respectively. Also, we
decode the $i$-th block of $E$ using rank and select queries on $E_{1}$ and
$E_{2}$. We then define $b_{e}$ as $F_{i}$ if the $i$-th block of $E$ is bad.
Otherwise, we define $b_{e}$ as the $i$-th good block of $E$. Next, we compute
$g(b_{u},b_{d},b_{e},0)$ in $O(1)$ time by referring to the precomputed table
$O(1)$ times, and prepend $0$ if we decode the first block of $B$. Finally,
note that there are at most $q\leq 4$ consecutive positions from $p$ to
$p+q-1$ of $B$ whose corresponding positions are the same in both $D$ and $E$.
Because such a case can only occur when $B[p]=B[p+1]=\dots=B[p+q-2]=1$ and
$B[p+q-1]=0$, we maintain an array $R$ of size $O(n/\log n)$, which stores the
four cases of the number of consecutive $1$’s ($0$, $1$, $2$, or at least $3$)
from the beginning of the $i$-th block of $B$. Then, if the number of
consecutive $1$’s from the beginning of $g(b_{u},b_{d},b_{e},0)$ is at most
$3$, we delete some $1$s from the beginning of $g(b_{u},b_{d},b_{e},0)$ by
referring to $R$ as the final step.

##  4 Data structure on general arrays

In this section, we present a $(3.701n+o(n))$-bit data structure to support
the range $q$-th minimum/maximum and next/previous larger/smaller value
queries on the array $A[1\dots,n]$ without any restriction. Let $C[1,\dots,n]$
be a bit array of size $n$ where $C[1]=0$, and for any $i>1$, $C[i]=1$ if and
only if $C[i-1]=C[i]$. If $C$ has $k$ ones, we define an array
$A^{\prime}[1,\dots,n-k]$ of size $n-k$ that discards all consecutive equal
elements from $A$. Then from the definition of colored 2d-min and max heap, we
can observe that if $C[i]=1$, (i) the node $i$ is a blue-colored leaf node,
and (ii) $i$’s immediate left sibling is also a leaf node, both in
$\textsf{cMin}{}(A)$ and $\textsf{cMax}{}(A)$. Furthermore, by deleting all
the bits at the positions $f(i,\textsf{cMin}{}(A))-1$, and
$f(i,\textsf{cMin}{}(A))$ from $\textsf{BP}{}(\textsf{cMin}{}(A))$ we can
obtain $\textsf{BP}{}(\textsf{cMin}{}(A^{\prime}))$. We can also obtain
$\textsf{BP}{}(\textsf{cMax}{}(A^{\prime}))$ from
$\textsf{BP}{}(\textsf{cMax}{}(A^{\prime}))$ analogously. Now we prove the
following theorem.

Figure 4: Combined data structure of $\textsf{cMin}{}(A)$ and
$\textsf{cMax}{}(A)$. Note that $A^{\prime}$ is the same array as the array in
Figure 3.

######  Theorem 4.1.

Given an array $A[1,\dots,n]$ of size $n$ and any positive integer $\ell$,
there exists a $(3.701n+o(n))$-bit encoding data structure which can answer
(i) range minimum/maximum and previous larger/smaller value queries in $O(1)$
time, and (ii) range $q$-th minimum/maximum and next larger/smaller value
queries in $O(\log^{(\ell)}n)$ time, for any $q\geq 1$.

###### Proof.

The data structure consists of $C$ and the data structure of Theorem 3.2 on
$A^{\prime}$, which can answer all the queries on $A^{\prime}$ in
$O(\log^{(\ell)}n)$ time (see Figure 4 for an example). By maintaining $C$
using the data structure of Lemma 3, the data structure takes at most $(2+\log
3)(n-k)+{n\choose k}+o(n)\leq 3.701n+o(n)$ bits in total [18] while supporting
rank and select queries on $C$ in $O(1)$ time. For any node $i$ in
$\textsf{cMin}{}(A)$ and $\textsf{cMax}{}(A)$, we can compute the color of the
node $i$ in $O(1)$ time as follows. If $C[i]=0$, we return the color of the
node $(\textsf{rank}{}_{0}(i,C)-1)$ in $\textsf{cMin}{}(A^{\prime})$ and
$\textsf{cMax}{}(A^{\prime})$, respectively. Otherwise, we return blue. Now we
describe how to decode any $\log n$ consecutive bits of
$\textsf{BP}(\textsf{cMin}{}(A))$ in $O(1)$ time using $o(n)$-bit auxiliary
structures, which proves the theorem (the auxiliary structures and the
procedure for decoding $\textsf{BP}(\textsf{cMax}{}(A))$ are analogous). In
the proof, we denote $\textsf{BP}(\textsf{cMin}{}(A))$ and
$\textsf{BP}(\textsf{cMin}{}(A^{\prime}))$ as $B$ and $B^{\prime}$,
respectively.

For each position $j$ of $B$, we say $j$ is original if $B[j]$ comes from the
bit in $B^{\prime}$, and additional otherwise. That is, the position $j$ is
additional if and only if $j$ is $f(j^{\prime})-1$ or $f(j^{\prime})$ where
$C[j^{\prime}]=1$. For each original position $j$, let $b^{\prime}(j)$ be its
corresponding position in $B^{\prime}$.

Now we divide $B$ into the blocks of size $\log n$ except the last block, and
let $s_{i}$ be the starting position of the $i$-th block of $B$. We then
define a bit array $M_{B^{\prime}}$ of size $2(n-k)$ as follows. For each
$i\in{1,\dots,\left\lceil(2(n+1)/\log n\right\rceil}$, we set the
$b^{\prime}(s_{i})$-th position of $M_{B^{\prime}}$ as one if $s_{i}$ is
original. Otherwise, we set the $b^{\prime}(s^{\prime}_{i})$-th position of
$M_{B^{\prime}}$ as one where $s^{\prime}_{i}$ is the leftmost original
position from $s_{i}$ to the right in $B$. All other bits in $M_{B^{\prime}}$
are $0$. Also, let $M^{\prime}_{B^{\prime}}$ a bit array of size
$\left\lceil(2(n+1)/\log n\right\rceil$ where $M^{\prime}_{B^{\prime}}[i]$ is
$1$ if and only if we mark the same position for $s_{i}$ and $s_{i-1}$. Since
$M_{B^{\prime}}$ has at most $\left\lceil(2(n+1)/\log n\right\rceil=o(n)$
ones, we can maintain both $M_{B^{\prime}}$ and $M^{\prime}_{B^{\prime}}$ in
$o(n)$ bits while supporting rank and select queries in $O(1)$ time by Lemma
3. Similarly, we define a bit array $M_{C}$ of size $n$ as follows. If $s_{i}$
is original, we set the $(\textsf{rank}{}_{0}(s_{i}-1,B))$-th position of
$M_{C}$ as one. Otherwise, we set the $(\textsf{rank}{}_{0}(s_{i}-1,B))$-th
(resp. $(\textsf{rank}{}_{0}(s_{i},B)$-th) position of $M_{C}$ as one if
$B[s_{i}]$ is $0$ (resp. $1$). We also maintain a bit array $M^{\prime}_{C}$
analogous to $M^{\prime}_{B^{\prime}}$. Again, we can maintain both $M_{C}$
and $M^{\prime}_{C}$ using $o(n)$ bits while supporting rank and select
queries on them in $O(1)$ time.

Next, let $h(b,c)$ be a function, which returns a subarray of $B$ from the
subarrays of $B^{\prime}$ and $C$, defined as follows (suppose $c=c[1]\cdot
c^{\prime}$):

$h(b,c)=\begin{cases}1^{t}&\text{if}~{}b=1^{t}~{}\text{and}~{}c[1]=0\\\
1^{t}0\cdot h(b^{\prime},c^{\prime})&\text{if}~{}b=1^{t}0\cdot
b^{\prime}~{}\text{and}~{}c[1]=0\\\ 10\cdot
h(b,c^{\prime})&\text{if}~{}c[1]=1\\\ \end{cases}$

We store a precomputed table, which stores $h(b,c)$ for all possible $b$, $c$
of size $\frac{1}{4}\log n$ using $O(2^{\frac{1}{2}\log n}\log
n)=O(\sqrt{n}\log n)=o(n)$ bits.

To decode the $i$-th block of $B$, we first decode $\log n$-sized subarrays of
$B^{\prime}$ and $C$, $b_{b^{\prime}}$ and $b_{c}$, whose starting positions
are
$\textsf{select}{}_{1}(\textsf{rank}{}_{0}(i,M^{\prime}_{B^{\prime}}),M_{B^{\prime}})$
and $\textsf{select}{}_{1}(\textsf{rank}{}_{0}(i,M^{\prime}_{C}),M_{C})$,
respectively. We then compute $h(b_{b^{\prime}},b_{c})$ in $O(1)$ time by
referring to the precomputed table $O(1)$ times. Finally, we store a bit array
of size $o(n)$, which indicates whether the first bit of the $i$-th block of
$B$ is $0$ or not. As the final step, we delete the leftmost bit of
$h(b_{b^{\prime}},b_{c})$ if the $i$-th block of $B$ starts from $0$, and
$s_{i}$ is additional (this can be done by referring to the bit array).

##  5 Lower bounds

This section considers the effective entropy to answer range $q$-th minimum
and maximum queries on an array of size $n$, for any $q\geq 1$. Note that for
any $i\in\\{1,\dots,n\\}$, both $\textsf{PSV}{}(i)$ and $\textsf{PLV}{}(i)$
queries can be answered by computing $q$-th range minimum and maximum queries
on the suffixes of the substring $A[1,\dots,i]$, respectively. Similarly, both
$\textsf{NSV}{}(i)$ and $\textsf{NLV}{}(i)$ queries can be answered by
computing $q$-th range minimum and maximum queries on the prefixes of the
substring $A[i,\dots,n]$, respectively.

Let $\mathcal{A}_{n}$ be a set of all arrays of size $n\geq 2$ constructed
from the following procedure:

  1. 1.

For any $0\leq k\leq n-1$, pick arbitrary $k$ positions in $\\{2,\dots,n\\}$,
and construct a Baxter Permutation [1] $\pi_{n-k}$ of size $n-k$ on the rest
of $n-k$ positions. Here, a Baxter permutation is a permutation that avoids
the patterns $2\scalebox{0.75}[1.0]{$-$}41\scalebox{0.75}[1.0]{$-$}3$ and
$3\scalebox{0.75}[1.0]{$-$}14\scalebox{0.75}[1.0]{$-$}2$.

  2. 2.

For $k$ picked positions, assign the rightmost element in $\pi_{n-k}$ to the
left.

Since the number of all possible Baxter permutations of size $n-k$ is at most
$2^{3(n-k)-\Theta(\log n)}$ [8], the effective entropy of $\mathcal{A}_{n}$ is
at least $\log|\mathcal{A}_{n}|\geq\log(\sum_{k=0}^{n-1}2^{3(n-k)-\Theta(\log
n)}\cdot{n-1\choose k})\geq\max{}_{k}(3n-3k+\log{n\choose k}-\Theta(\log
n))\geq n\log 9-\Theta(\log n)\geq 3.16n-\Theta(\log n)$ bits [18]. The
following theorem shows that the effective entropy of the encoding to support
the range $q$-th minimum and maximum queries on an array of size $n$ is at
least $3.16n-\Theta(\log n)$ bits.

######  Theorem 5.1.

Any array $A$ in $\mathcal{A}_{n}$ for $n\geq 2$ can be reconstructed using
range $q$-th minimum and maximum queries on $A$.

###### Proof.

We follow the same argument used in the proof of Lemma 3 in [8], which shows
that one can reconstruct any Baxter permutation of size $n$ using range
minimum and maximum queries.

The proof is induction on $n$. the case $n=2$ is trivial since only the
possible cases are $\\{1,1\\}$ or $\\{1,2\\}$, which can be decoded by range
first and second minimum queries. Now suppose the theorem statement holds for
any size less than $n\geq 3$. Then, both $A_{1}=A[1,\dots,n-1]$ and
$A_{2}=A[2,\dots,n]$ from $\mathcal{A}_{n-1}$ can be reconstructed by the
induction hypothesis. Thus, to reconstruct $A$ from $A_{1}$ and $A_{2}$, it is
enough to compare $A[1]$ and $A[n]$.

If any answer of $\textsf{RMax}{}(1,n,q)$ and $\textsf{RMin}{}(1,n,q)$
contains the position $1$ or $n$, we are done. Otherwise, let $x$ and $y$ be
the rightmost positions of the smallest and largest element in $[2,n-1]$,
which can be computed by $\textsf{RMax}{}(1,n,q)$ and
$\textsf{RMin}{}(1,n,q)$, respectively. Without a loss of generality, suppose
$x<y$ (other case is symmetric). In this case, [8] showed that (i) there
exists a position $i\in[x,y]$, which satisfies $A[1]<A[i]<A[n]$ or
$A[1]>A[i]>A[n]$, or (ii) $A[1]<A[n]$, which proves the theorem (note that
$A[1]$ cannot be equal to $A[n]$ in this case since the same elements in $A$
always appear consecutively).

##  6 Conclusion

This paper proposes an encoding data structure that efficiently supports range
($q$-th) minimum/maximum queries and next/previous larger/smaller value
queries. Our results match the current best upper bound of Tsur [18] up to
lower-order additive terms while supporting the queries efficiently.

Note that the lower bound of Theorem 5.1 only considers the case that the same
elements always appear consecutively, which still gives a gap between the
upper and lower bound of the space. Improving the lower bound of the space for
answering the queries would be an interesting open problem.

### Acknowledgements

This work was supported by the National Research Foundation of Korea (NRF)
grant funded by the Korea government (MSIT) (No. NRF-2020R1G1A1101477). We
would like to thank to Srinivasa Rao Satti for helpful discussions.

## References

  * [1] Baxter, G.: On fixed points of the composite of commuting functions. Proceedings of the American Mathematical Society 15(6), 851–855 (1964)
  * [2] Benoit, D., Demaine, E.D., Munro, J.I., Raman, R., Raman, V., Rao, S.S.: Representing trees of higher degree. Algorithmica 43(4), 275–292 (2005)
  * [3] Berkman, O., Schieber, B., Vishkin, U.: Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values. J. Algorithms 14(3), 344–370 (1993)
  * [4] Dodis, Y., Patrascu, M., Thorup, M.: Changing base without losing space. In: STOC 2010. pp. 593–602. ACM (2010)
  * [5] Ferrada, H., Navarro, G.: Improved range minimum queries. In: 2016 Data Compression Conference, DCC 2016. pp. 516–525. IEEE (2016)
  * [6] Fischer, J.: Combined data structure for previous- and next-smaller-values. Theor. Comput. Sci. 412(22), 2451–2456 (2011)
  * [7] Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput. 40(2), 465–492 (2011)
  * [8] Gawrychowski, P., Nicholson, P.K.: Optimal encodings for range top- k k , selection, and min-max. In: ICALP 2015, Proceedings, Part I. Lecture Notes in Computer Science, vol. 9134, pp. 593–604. Springer (2015)
  * [9] Jo, S., Satti, S.R.: Simultaneous encodings for range and next/previous larger/smaller value queries. Theor. Comput. Sci. 654, 80–91 (2016)
  * [10] Merlini, D., Sprugnoli, R., Verri, M.C.: Waiting patterns for a printer. Discret. Appl. Math. 144(3), 359–373 (2004)
  * [11] Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Comput. 31(3), 762–776 (2001)
  * [12] Munro, J.I., Raman, V., Rao, S.S.: Space efficient suffix trees. J. Algorithms 39(2), 205–222 (2001)
  * [13] Navarro, G., Sadakane, K.: Fully functional static and dynamic succinct trees. ACM Trans. Algorithms 10(3), 16:1–16:39 (2014)
  * [14] Ohlebusch, E., Fischer, J., Gog, S.: CST++. In: SPIRE 2010. Proceedings. Lecture Notes in Computer Science, vol. 6393, pp. 322–333. Springer (2010)
  * [15] Raman, R.: Encoding data structures. In: WALCOM 2015. Proceedings. Lecture Notes in Computer Science, vol. 8973, pp. 1–7. Springer (2015)
  * [16] Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding _k_ -ary trees, prefix sums and multisets. ACM Trans. Algorithms 3(4), 43 (2007)
  * [17] Sadakane, K.: Succinct data structures for flexible text retrieval systems. J. Discrete Algorithms 5(1), 12–22 (2007)
  * [18] Tsur, D.: The effective entropy of next/previous larger/smaller value queries. Inf. Process. Lett. 145, 39–43 (2019)
  * [19] Vuillemin, J.: A unifying look at data structures. Commun. ACM 23(4), 229–239 (1980)