## Abstract

We consider the problem of *encoding range minimum queries* (RMQs): given an array *A*[1..*n*] of distinct totally ordered values, to pre-process *A* and create a data structure that can answer the query RMQ(*i*,*j*), which returns the index containing the smallest element in *A*[*i*..*j*], *without* access to the array *A* at query time. We give a data structure whose space usage is 2*n*+*o*(*n*) bits, which is asymptotically optimal for worst-case data, and answers RMQs in *O*(1) worst-case time. This matches the previous result of Fischer and Heun, but is obtained in a more natural way. Furthermore, our result can encode the RMQs of a random array *A* in 1.919*n*+*o*(*n*) bits in expectation, which is not known to hold for Fischer and Heun’s result. We then generalize our result to the encoding *range top-2 query* (RT2Q) problem, which is like the encoding RMQ problem except that the query RT2Q(*i*,*j*) returns the indices of both the smallest and second smallest elements of *A*[*i*..*j*]. We introduce a data structure using 3.272*n*+*o*(*n*) bits that answers RT2Qs in constant time, and also give lower bounds on the *effective entropy* of the RT2Q problem.

## 1. Introduction

Given an array *A*[1..*n*] of elements from a totally ordered set, the *range minimum query* (RMQ) problem is to pre-process *A* and create a data structure so that the query RMQ(*i*,*j*), which takes two indices 1≤*i*≤*j*≤*n* and returns argmin_{i≤k≤j}*A*[*k*], is supported efficiently (in terms of both space and time). We consider the *encoding* version of this problem: after pre-processing *A*, the data structure should answer RMQs *without* access to *A*; in other words, the data structure should encode all the information about *A* needed to answer RMQs. In many applications that deal with storing and indexing massive data, the values in *A* have no intrinsic significance and *A* can be discarded after pre-processing (e.g. *A* may contain scores that are used to determine the relative order of documents returned in response to a search query). As we now discuss, the encoding of *A* for RMQs can often take much less space than *A* itself, so encoding RMQs can facilitate the efficient in-memory processing of massive data.

It is well known [1] that the RMQ problem is equivalent to the problem of supporting lowest common ancestor (LCA) queries on a binary tree, the *Cartesian* tree of *A* [2]. The Cartesian tree of *A* is a binary tree with *n* nodes, in which the root is labelled by *i*, where *A*[*i*] is the minimum element in *A*; the left subtree of the root is the Cartesian tree of *A*[1..*i*−1] and the right subtree of the root is the Cartesian tree of *A*[*i*+1..*n*]. The answer to RMQ(*i*,*j*) is the label of the LCA of the nodes labelled by *i* and *j*. Thus, knowing the topology of the Cartesian tree of *A* suffices to answer RMQs on *A*.

Farzan & Munro [3] showed that an *n*-node binary tree can be represented in 2*n*+*o*(*n*) bits, while supporting LCA queries in *O*(1) time.^{1} Unfortunately, this does not solve the RMQ problem. The difficulty is that nodes in the Cartesian tree are labelled with the index of the corresponding array element, which is equal to the node’s rank in the inorder traversal of the Cartesian tree. A common feature of *succinct* tree representations, such as that of [3], is that they do not allow the user to specify the numbering of nodes [4], and whereas existing succinct binary tree representations support numberings such as level-order [5] and pre-order [3], they do not support inorder. Indeed, for this reason, Fischer & Heun [6] solved the problem of optimally encoding the RMQ problem via an ordered rooted tree, rather than via the more natural Cartesian tree.

Our first contribution is to describe how, using *o*(*n*) additional bits, we can add the functionality below to the 2*n*+*o*(*n*)-bit representation of Farzan and Munro:

— node-rank

_{inorder}(*x*): returns the position in inorder of node*x*;— node-select

_{inorder}(*y*): returns the node*z*whose inorder position is*y*.

Here, *x* and *z* are node numbers in the node numbering scheme of Farzan and Munro, and both operations take *O*(1) time. Using this, we can encode RMQs of an array *A* using 2*n*+*o*(*n*) bits, and answer RMQs in *O*(1) time as follows. We represent the Cartesian tree of *A* using the representation of Farzan and Munro, augmented with the above operations, and answer RMQ(*i*,*j*) as
We thus match asymptotically the result of Fischer & Heun [6], while using a more direct approach. Furthermore, using our approach, we can encode RMQs of a random permutation using 1.919*n*+*o*(*n*) bits in expectation and answer RMQs in *O*(1) time. It is not clear how to obtain this result using the approach of Fischer and Heun.

Our next contribution is to consider a generalization of RMQs, namely to pre-process a totally ordered array *A*[1..*n*] to answer *range top-2 queries* (RT2Qs). The query RT2Q(*i*,*j*) returns the indices of the minimum as well as the second minimum values in *A*[*i*..*j*]. Again, we consider the encoding version of the problem, so that the data structure does not have access to *A* when answering a query. Encoding problems, such as the RMQ and RT2Q, are fundamentally about determining the *effective entropy* of the data structuring problem [7]. Given the input data drawn from a set of inputs , and a set of queries *Q*, the effective entropy of *Q* is , where is the set of equivalence classes on induced by *Q*, whereby two objects from are equivalent if they provide the same answer to all queries in *Q*. For the RMQ problem, it is easy to see that every binary tree is the Cartesian tree of some array *A*. Because there are *C*_{n}=(1/*n*+1)(2*n* *n*) *n*-node binary trees, the effective entropy of the RMQ problem is exactly bits.

The effective entropy of the more general *range top- k problem*, or finding the indices of the

*k*smallest elements in a given range

*A*[

*i*,

*j*], was recently shown to be bits by Grossi

*et al.*[8]. However, for

*k*=2, their approach only shows that the effective entropy of the RT2Q problem is ≥

*n*/2—much less than the effective entropy of the RMQ problem. Using an encoding based upon merging paths in Cartesian trees, we show that the effective entropy of the RT2Q problem is at least bits. We show that this effective entropy applies also to the (apparently) easier problem of returning just the second minimum in an array interval, R2M(

*i*,

*j*). We complement this result by giving a data structure for encoding RT2Qs that takes 3.272

*n*+

*o*(

*n*) bits and answers queries in

*O*(1) time. This structure builds upon our new 2

*n*+

*o*(

*n*)-bit RMQ encoding by adding further functionality to the binary tree representation of Farzan and Munro. We note that the range top-

*k*encoding of Grossi

*et al.*[8] builds upon an encoding that answers RT2Qs in

*O*(1) time, but their encoding for this subproblem uses 6

*n*+

*o*(

*n*) bits.

### (a) Preliminaries

Given a bit vector *B*[1..*m*], rank_{B}(1,*i*) returns the number of 1s in *B*[1..*i*], and select_{B}(1,*i*) returns the position of the *i*th 1 in *B*. The operations rank_{B}(0,*i*) and select_{B}(0,*i*) are defined analogously for 0s. A data structure that supports the operations rank and select is a building block of many succinct data structures. Lemma 1.1 states a rank–select data structure that we use to obtain our results.

### Lemma 1.1

[Clark [9] and Munro 10] Given a bit vector *B*[1..*m*], there exists a data structure of size *m*+*o*(*m*) bits that supports rank_{B}(1,*i*), rank_{B}(0,*i*), select_{B}(1,*i*), and select_{B}(0,*i*) in *O*(1) time.

We also use lemma 1.2, which states a more space-efficient rank–select data structure that assumes the number of 1s in *B* is known.

### Lemma 1.2

[Raman *et al.* 11] Given a bit vector *B*[1..*m*] that contains *n* 1s, there exists a data structure of size bits that supports rank_{B}(1,*i*), rank_{B}(0,*i*), select_{B}(1,*i*), and select_{B}(0,*i*) in *O*(1) time.

## 2. Representation based on tree decomposition

We now describe a succinct representation of binary trees that supports a comprehensive list of operations [12,13,3].^{2} The structure of Farzan & Munro [3] supports multiple orderings on the nodes of the tree, including pre-order, post-order and DFUDS (depth first unary degree sequence) order by providing the operations node-rank_{pre-order}(*v*), node-select_{pre-order}(*v*), node-rank_{post-order}(*v*), node-select_{post-order}(*v*), node-rank_{DFUDS}(*v*) and node-select_{DFUDS}(*v*). We provide two additional operations, node-rank_{inorder}(*v*) and node-select_{inorder}(*v*), thereby also supporting inorder numbering on the nodes.

Our data structure consists of two parts: (i) the data structure of Farzan & Munro [3] and (ii) an additional structure we construct to specifically support node-rank_{inorder} and node-select_{inorder}. In the following, we outline the first part (refer to Farzan & Munro [3] for more details), and then we explain in detail the second part.

### (a) Succinct cardinal trees of Farzan & Munro

Farzan & Munro [3] reported a succinct representation of cardinal trees (*k*-ary trees). Because binary trees are a special case of cardinal trees (when *k*=2), their data structure can be used as a succinct representation of binary trees. Lemma 2.1 states their result for binary trees.

### Lemma 2.1

[Farzan & Munro 3] A binary tree with *n* nodes can be represented using 2*n*+*o*(*n*) bits of space, whereas a comprehensive list of operations [3], table 2 (or see footnote 2) can be supported in *O*(1) time.

This data structure is based on a tree decomposition similar to previous ones [14,12,15]. An input binary tree is first partitioned into *mini-trees* each of size at most , which are disjoint aside from their roots. Each mini-tree is further partitioned (recursively) into *micro-trees* of size at most , which are also disjoint aside from their roots. A *boundary node* of a mini tree is a non-root node of the mini-tree that has a child located in a different mini-tree (similarly, a boundary node is defined for micro-trees).

The decomposition algorithm achieves the following prominent property: each mini-tree has at most one boundary node, and each boundary node has at most one child located in a different mini-tree (a similar property holds for micro-trees). This property implies that, aside from the edges on the mini-tree roots, there is at most one edge in each mini-tree that connects a node of the mini-tree to its child in another mini-tree. These properties also hold for micro-trees.

It is well known that the topology of a tree with *k* nodes can be described with a fingerprint of size 2*k* bits. Because the micro-trees are small enough, the operations within the micro-trees can be performed by using a universal look-up table of size *o*(*n*) bits, where the fingerprints of micro-trees are used as indexes into the table.

The binary tree representation consists of the following parts (apart from the look-up table): (i) representation of each micro-tree: its size and fingerprint; (ii) representation of each mini-tree: links between the micro-trees within the mini-tree; and (iii) links between the mini-trees. The overall space of this data structure is 2*n*+*o*(*n*) bits [3].

### (b) Data structure for node-rank_{inorder} and node-select_{inorder}

We present a data structure that is added to the structure of lemma 2.1 in order to support node-rank_{inorder} and node-select_{inorder}. This additional data structure contains two separate parts, each to support one of the operations. In the following, we describe each of these two parts. Note that we have access to the succinct binary tree representation of lemma 2.1.

#### (i) Operation node-rank_{inorder}

We present a data structure that can compute the inorder number of a node *v*, given its pre-order number. Our method is based on the fact that the difference between the inorder number and the pre-order number of *v* is equal to the difference between the following two values: (i) the number of nodes located in the left subtree of *v*, which can be computed by subtree-size(*v*_{l}), where *v*_{l} is the left child of *v*; and (ii) Ldepth(*v*): the number of ancestors of *v* whose left child is also on the *v*-to-root path (in other words, the number of left-turns in the *v*-to-root path). Formally, we use the following equation: inorder(*v*)=pre-order(*v*)+subtree-size(*v*_{l})−Ldepth(*v*).

In the following, we explain how to compute Ldepth(*v*), which is similar to computing the depth of a node. This operation is also used in §3. For the root *r*_{m} of each mini-tree, we pre-compute and store Ldepth(*r*_{m}), which requires bits. Let mini-Ldepth(*v*) and micro-Ldepth(*v*) be the number of left turns from a node *v* up to the root of, respectively, the mini-tree and micro-tree containing *v*. For the root *r*_{μ} of each micro-tree, we pre-compute and store mini-Ldepth(*r*_{μ}). We use a look-up table to compute micro-Ldepth(*v*) for every node *v*. Finally, to compute Ldepth(*v*), we simply calculate Ldepth(*r*_{m})+mini-Ldepth(*r*_{μ})+micro-Ldepth(*v*), where *r*_{m} and *r*_{μ} are the root of, respectively, the mini-tree and micro-tree containing *v*. The data structure of lemma 2.1 can be used to find *r*_{m} and *r*_{μ} and the calculation can be done in *O*(1) time.

#### (ii) Operation node-select_{inorder}

We present a data structure that can compute the pre-order number of a node *v*, given its inorder number. To compute the pre-order number of *v*, we compute (i) the pre-order number of the root *r*_{m} of the mini-tree containing *v* and (ii) *c*(*v*,*r*_{m}): the number of nodes that are visited after *r*_{m} and before *v* in pre-order traversal, which may include nodes both within and outside the mini-tree rooted at *r*_{m}. Observe that the pre-order number of *v* is equal to the pre-order number of *r*_{m} plus *c*(*v*,*r*_{m}). In the following, we explain how to compute these two quantities.

(1) We pre-compute the pre-order numbers of all the mini-tree roots and store them in *P*[0..*n*_{m}−1] in some arbitrary order defined for mini-trees, where is the number of mini-trees. Note that each mini-tree now has a *rank* from [0..*n*_{m}−1]. Later on, when we want to retrieve the pre-order number of the root of the mini-tree containing *v*, we need only to determine the rank *i* of the mini-tree and read the answer from *P*[*i*]. In the following, we explain a data structure that supports finding the rank of the mini-tree containing any given node *v*.

In the pre-processing, we construct a bit-vector *A* and an array *B* of mini-tree ranks, which are initially empty, by traversing the input binary tree in inorder as follows (see figure 1 for an example).

For *A*, we append a bit for each visited node and thus the length of *A* is *n*. If the current visited node and the previous visited node are in two different mini-trees, then the appended bit is 1, and otherwise 0; if a mini-tree root is common among two mini-trees, then its corresponding bit is 0 (i.e. the root is considered to belong to the mini-tree containing its left subtree, because a common root is always visited after its left subtree is visited); the first bit of *A* is always a 1.

For *B*, we append the rank of each visited mini-tree; more precisely, if the current visited node and the previous visited node are in two different mini-trees, then we append the rank of the mini-tree containing the current visited node, and otherwise we append nothing. Similarly, a common root is considered to belong to the mini-tree containing its left subtree; the first rank in *B* is the rank of the mini-tree containing the first visited node.

We observe that a node *v* with inorder number *i* belongs to the mini-tree with rank *B*[rank_{A}(1,*i*+1)], and thus *P*[*B*[rank_{A}(1,*i*+1)]] contains the pre-order number of the root of the mini-tree containing *v*.

We represent *A* using the data structure of lemma 1.2, which supports rank in constant time. In order to analyse the space, we prove that the number of 1s in *A* is at most 2*n*_{m}: each mini-tree has at most one edge leaving the mini-tree aside from its root, which means that the traversal can enter or re-enter a mini-tree at most twice. Therefore, the space usage is bits, as . We store *P* and *B* explicitly with no pre-processing on them. The length of *B* is also at most 2*n*_{m} by the same argument. Thus, both *P* and *B* take bits.

(2) Let *S* be the set of nodes that are visited after *r*_{m} and before *v* in the pre-order traversal of the tree. Note that *c*(*v*,*r*_{m})=|*S*|. Let *t*_{m} and *t*_{μ} be, respectively, the mini-tree and micro-tree containing *v*. We note that *S*=*S*_{1}∪*S*_{2}∪*S*_{3}, where *S*_{1} contains the nodes of *S* that are not in *t*_{m}, *S*_{2} contains the nodes of *S* that are in *t*_{μ}, and *S*_{3} contains the nodes that are in *t*_{m} and not in *t*_{μ}. Observe that *S*_{1}, *S*_{2} and *S*_{3} are mutually disjoint. Therefore, *c*(*v*,*r*_{m})=|*S*_{1}|+|*S*_{2}|+|*S*_{3}|. We now describe how to compute each size.

*S*_{1}: if*t*_{m}has a boundary node which is visited before the root of*t*_{μ}, then |*S*_{1}| is the subtree size of the child of the boundary node that is out of*t*_{m}; otherwise, |*S*_{1}|=0.*S*_{2}: because these nodes are within a micro-tree, |*S*_{2}| can be computed using a look-up table.*S*_{3}: the local pre-order number of the root of*t*_{μ}, which results from traversing*t*_{m}while ignoring the edges leaving*t*_{m}, is equal to |*S*_{3}|. We pre-compute the local pre-order numbers of all the micro-tree roots. The method to store these local pre-order numbers and the data structure that we construct in order to efficiently retrieve these numbers is similar to part (1), whereas here a mini-tree plays the role of the input tree and micro-trees play the role of the mini-trees. In other words, we construct*P*,*A*and*B*of part (1) for each mini-tree. The space usage of this data structure is*o*(*n*) bits by the same argument, regarding the fact that each local pre-order number takes bits.

### Theorem 2.2

*A binary tree with n nodes can be represented with a succinct data structure of size 2n+o(n) bits, which supports node-rank*_{inorder}*, node-select*_{inorder}*, plus a comprehensive set of operations [*3*], table 2, all in O(1) time.*

### (c) Range minimum queries on random inputs

Theorem 2.3 gives a slight generalization of theorem 2.2, which uses entropy coding to exploit any differences in frequency between different types of nodes (theorem 2.2 corresponds to choosing all the *α*_{i}s to be 1/4 in the following).

### Theorem 2.3

*For any positive constants α*_{0}*,α*_{L}*,α*_{R} *and α*_{2}*, such that α*_{0}*+α*_{L}*+ α*_{R}*+α*_{2}*=1, a binary tree with n*_{0} *leaves, n*_{L} *(n*_{R}*) nodes with only a left (right) child and n*_{2} *nodes with both children can be represented using* *bits of space, while a full set of operations [*3*], table 2 including node-rank*_{inorder}*, node-select*_{inorder} *and LCA can be supported in O(1) time.*

### Proof.

We proceed as in the proof of theorem 2.2, but if , then we choose the size of the micro-trees to be at most . The 2*n*-bit term in the representation of [3] comes from the representation of the micro-trees. Given a micro-tree with *μ*_{i} nodes of type *i*, for *i*∈{0,*L*,*R*,2} we encode it by writing the node types in level order (cf. [5]) and encoding this string using arithmetic coding with the probability of a node of type *i* taken to be *α*_{i}. The size of this encoding is at most bits, from which the theorem follows. Note that our choice of *μ* guarantees that each micro-tree fits in bits and thus can still be manipulated using universal look-up tables.

### Corollary 2.4

If *A* is a random permutation over {1,…,*n*}, then RMQs on *A* can be answered using bits in expectation.

### Proof.

Choose *α*_{0}=*α*_{2}=1/3 and *α*_{R}=*α*_{L}=1/6. The claim follows from the fact that *α*_{i}*n* is the average value of *n*_{i} on random binary trees, for any *i*∈{0,*L*,*R*,2} [16], theorem 1.

While both our representation and that of Fischer & Heun [6] solve RMQs in *O*(1) time and use 2*n*+*o*(*n*) bits in the worst case, ours allows an improvement in the average case. However, we are unable to match the expected effective entropy of the RMQ problem on random arrays *A*, which is bits [7], theorem 1 (see also [17]).

It is natural to ask whether one can obtain improvements for the average case also via Fischer & Heun’s approach [6]. Their approach first converts the Cartesian tree to an *ordinal tree* (an ordered, rooted tree) using the textbook transformation [18]. To the best of our knowledge, the only ordinal tree representation able to use (2−*Θ*(1))*n* bits is the so-called *ultra-succinct* representation [19], which uses bits, where *n*_{a} is the number of nodes with *a* children. Our empirical simulations suggest that the combination of [6] with [19] would not use (2−*Ω*(1))*n* bits on average on random permutations. We generated random permutations of sizes 10^{3} to 10^{7} and measured the entropy on the resulting Cartesian trees. The results, averaged over 100 to 1000 iterations, are 1.991916, 1.998986, 1.999869, 1.999984 and 1.999998, respectively. The results appear as a straight line on a log–log plot, which suggests a formula of the form 2*n*−*f*(*n*) for a very slowly growing function *f*(*n*). Indeed, using the model we obtain the approximation with a mean squared error below 10^{−9}.

To understand the observed behaviour, first note that, when the Cartesian tree is converted to an ordinal tree, the arity of each ordinal tree node *u* turns out to be, in the Cartesian tree, the length of the path from the right child *v* of *u* to the left-most descendant of *v* (i.e. the node representing *u*+1 if we identify Cartesian tree nodes with their positions in *A*). This is called *r*_{u} (or *L*_{v}) in the next section. Next, note the following.

### Lemma 2.5

The probability that a node *v* of the Cartesian tree of a random permutation has a left child is 1/2.

### Proof.

Consider the values *A*[*v*−1] and *A*[*v*]. If *A*[*v*]<*A*[*v*−1], then RMQ(*v*−1,*v*)= *v*=LCA(*v*−1,*v*), thus *v*−1 descends from *v* and hence *v* has a left child. If *A*[*v*]>*A*[*v*−1], then RMQ(*v*−1,*v*)=*v*−1=LCA(*v*−1,*v*), thus *v* descends from *v*−1 and hence *v* is the left-most node of the right subtree of *v*−1, and therefore *v* cannot have a left child. Therefore, *v* has a left child iff *A*[*v*]<*A*[*v*−1], which happens with probability 1/2 in a random permutation.

Thus, if we disregarded the dependencies between nodes in the tree, then we could regard *L*_{v} as a geometrical variable with parameter 1/2, and thus the expected value of *n*_{a} would be . Taking the expectation as a fixed value, the space would be . Although this is only a heuristic argument (as we are ignoring both the dependencies between tree nodes and the variance of the random variables), our empirical results nevertheless suggest that this simplified model is asymptotically accurate, and, thus, that no space advantage is obtained by representing random Cartesian trees, as opposed to worst-case Cartesian trees, using this scheme.

## 3. Range top-2 queries

Here, we consider a generalization of the RMQ problem. Again, let *A*[1..*n*] be an array of elements from a totally ordered set. Let R2M(*i*,*j*), for any 1≤*i*<*j*≤*n*, denote the position of the second smallest value in *A*[*i*..*j*]. More formally
The *encoding RT2Q* problem is to pre-process *A* into a data structure that, given *i*,*j*, returns RT2Q(*i*,*j*)=(RMQ(*i*,*j*),R2M(*i*,*j*)), without accessing *A* at query time.

The idea is to augment the Cartesian tree of *A*, denoted *T*_{A}, with some information that allows us to answer R2M(*i*,*j*). If *h* is the position of the minimum element in *A*[*i*..*j*] (i.e. *h*=RMQ(*i*,*j*)), then *h* divides [*i*..*j*] into two subranges [*i*..*h*−1] and [*h*+1..*j*], and the second minimum is the smaller of the elements *A*[RMQ(*i*,*h*−1)] and *A*[RMQ(*h*+1,*j*)]. Except for the case where one of the subranges is empty, the answer to this comparison is not encoded in *T*_{A}. We describe how to succinctly encode the ordering between the elements of *A* that are candidates for R2M(*i*,*j*). Our data structure consists of this encoding together with the encoding of *T*_{A} using the representation of theorem 2.2 (along with the operations mentioned in §2).

We define the *left spine* of a node *u* to be the set of nodes on the downward path from *u* (inclusive) that follows left children until this can be done no further. The right spine of a node is defined analogously. The *left inner spine* of a node *u* is the right spine of *u*’s left child. If *u* does not have a left child, then it has an empty left inner spine. The right inner spine is defined analogously. We use the notations lspine(*v*)/rspine(*v*), lispine(*v*)/rispine(*v*), *L*_{v}/*R*_{v} and *l*_{v}/*r*_{v} to denote the left/right spines of *v*, the left/right inner spines of *v*, and the number of nodes in the spines and inner spines of *v*, respectively. We also assume that nodes are numbered in inorder and identify node names with their inorder numbers.

As previously mentioned, our data structure encodes the ordering between the candidates for R2M(*i*,*j*). We first identify locations for these candidates, as follows.

### Lemma 3.1

In *T*_{A}, for any *i*,*j*∈[1..*n*], *i*<*j*, R2M(*i*,*j*) is located in lispine(*v*) or rispine(*v*), where *v*=RMQ(*i*,*j*).

### Proof.

Let *v*=RMQ(*i*,*j*). The second minimum clearly lies in one of two subranges [*i*..*v*−1] and [*v*+1..*j*], and it must be equal to either RMQ(*i*,*v*−1) or RMQ(*v*+1,*j*). W.l.o.g. assume that [*i*..*v*−1] is non-empty: in this case, the node *v*−1 is the bottom-most node on lispine(*v*). Furthermore, because *v*=RMQ(*i*,*j*), *i* must lie in the left subtree of *v*. Because the LCA of the bottom-most node on lispine(*v*) and any other node in the left subtree of *v* is a node in lispine(*v*), RMQ(*i*,*v*−1) is in lispine(*v*). The analogous statement holds for rispine(*v*).

Thus, for any node *v*, it suffices to store the relative order between nodes in lispine(*v*) and rispine(*v*) to find R2M(*i*,*j*) for all queries for which *v* is the answer to the RMQ. As *T*_{A} determines the ordering among the nodes of lispine(*v*) and also among the nodes of rispine(*v*), we need only to store the information needed to *merge* lispine(*v*) and rispine(*v*). We do this by storing bits associated with *v*, for all nodes *v*, as explained later. We need to bound the total space required for the ‘merging’ bits as well as to space efficiently realize the association of *v* with the *m*_{v} merging bits associated with it. For this, we need the following auxiliary lemmas.

### Lemma 3.2

Let *T* be a binary tree with *m* nodes (of which *m*_{0} are leaves) and root *τ*. Then, and .

### Proof.

The first part follows from the fact that the *R*_{τ} nodes in rspine(*τ*) do not appear in lispine(*v*) for any *v*∈*T*, and all the other nodes in *T* appear exactly once in a left inner spine. Similarly, the *L*_{τ} nodes in lspine(*τ*) do not appear in rispine(*v*) for any *v*∈*T*, and the other nodes in *T* appear exactly once in a right inner spine. Then, the second part follows from the fact that *m*_{v}=*l*_{v}+*r*_{v}−1 iff *l*_{v}+*r*_{v}>0, that is, *v* is not a leaf. If *v* is a leaf, then *l*_{v}+*r*_{v}=0=*m*_{v}. Thus, we must subtract *m*−*m*_{0} from the previous formula, which is the number of non-leaf nodes in *T*.

In lemma 3.3, we use two operations Ldepth(*v*) and Rdepth(*v*), which compute the number of nodes that have their left and right child, respectively, in the path from root to *v* (recall that Ldepth(*v*) is also used in §2). Note that depth(*v*)=Ldepth(*v*)+Rdepth(*v*) for any node *v*.

### Lemma 3.3

Let *T* be a binary tree with *m* nodes and root *τ*. Suppose that the nodes of *T* are numbered 0,…,*m*−1 in inorder. Then, for any 0≤*u*<*m*,

### Proof.

The proof is by induction on *m*. For the base case *m*=1, *τ*=*u*=0 is the only possibility and the formula evaluates to 0 as expected: *l*_{u}=Ldepth(*u*)=Rdepth(*u*)= 0 and *L*_{τ}=1 (recall that *τ* is included in lspine(*τ*)).

Now consider a tree *T* with root *τ* and *m*>1 nodes. We consider the three cases *u*=*τ*, *u*<*τ* and *u*>*τ* in that order. If *u*=*τ*, then Ldepth(*τ*)=Rdepth(*τ*)=0. If *τ* has no left child, then the situation is the same as when *m*=1. Else, letting *v* be the left child of *τ*, note that *L*_{v}=*L*_{τ}−1 and, because lispine(*τ*)=rspine(*v*), *l*_{τ}=*R*_{v}. As the subtree rooted at *v* has size exactly *τ*, the formula can be rewritten as 2*τ*−*L*_{v}−*R*_{v}, its correctness follows from lemma 3.2 without recourse to the inductive hypothesis.

If *u*<*τ*, then by induction on the subtree rooted at the left child *v* of *τ*, the formula gives 2*u*−*L*_{v}−*l*_{u}+Ldepth′(*u*)−Rdepth′(*u*)+1, where Rdepth′ and Ldepth′ are measured with respect to *v*. As Ldepth′(*u*)=Ldepth(*u*)−1, Rdepth′(*u*)=Rdepth(*u*) and *L*_{v}=*L*_{τ}−1, this equals 2*u*−*L*_{τ}−*l*_{u}+Ldepth(*u*)−Rdepth(*u*)+1 as required.

Finally, we consider the case *u*>*τ*. Letting *v* and *w* be the left and right children of *τ*, and *u*′=*u*−*τ*−1, we note that *u*′ is the inorder number of *u* in the subtree rooted at *w*. Applying the induction hypothesis to the subtree rooted at *w*, we obtain that
where Rdepth′ and Ldepth′ are measured with respect to *w*. Simplifying
Here, we have made use (in order) of lemma 3.2 and the facts Ldepth′(*u*)=Ldepth(*u*) and Rdepth′(*u*)=Rdepth(*u*)−1; *L*_{w}=*r*_{τ} and *R*_{v}=*l*_{τ}; and finally *L*_{v}=*L*_{τ}−1.

### Corollary 3.4

In the same scenario of lemma 3.3, we have
where Lleaves(*u*) denotes the number of leaves that appear before *u* in the inorder traversal.

### Proof.

Note that , and the latter is equal to using lemma 3.3 (because if *j* is not a leaf, and also because there are (*u*−Lleaves(*u*)) non-leaf nodes that appear before *u* in the inorder traversal).

*The data structure.* For each node *u* in *T*_{A}, we create a bit sequence *M*_{u} of length *m*_{u} to encode the merge order of lispine(*u*) and rispine(*u*). *M*_{u} is obtained by taking the sequence of all the elements of lispine(*u*)∪rispine(*u*) sorted in decreasing order, and replacing each element of this sorted sequence by 0 if the element comes from lispine(*u*) and by 1 if the element comes from rispine(*u*) (the last bit is omitted, as it is unnecessary). We concatenate the bit sequences *M*_{u} for all *u*∈*T*_{A} considered in inorder and call the concatenated sequence *M*.

The data structure comprises *M*, augmented with *rank* and *select* operations and a data structure for *T*_{A}. If we use theorem 2.2, then *T*_{A} is represented in 2*n*+*o*(*n*) bits, and the (augmented) *M* takes at most 1.5*n*+*o*(*n*) bits by lemmas 3.2 and 1.1, because there are at most (*n*+1)/2 leaves in an *n*-node binary tree. This gives a representation whose space is 3.5*n*+*o*(*n*) bits. A further improvement can be obtained by using theorem 2.3 as follows. For some real parameter 0<*x*<1, consider the concave function
Differentiating and simplifying, we obtain the maximum of *H*(*x*) as the solution to the equation , from which we obtain that *H*(*x*) is maximized at , and attains a maximum value of .

Now let *n*_{0},*n*_{L}(*n*_{R}) and *n*_{2} be the numbers of leaves, nodes with only a left (right) child and nodes with both children in *T*_{A}. Letting *x*=*n*_{0}/*n*, we apply theorem 2.3 to represent *T*_{A}, using the parameters *α*_{0}=*α*_{2} to be equal to *x*, but capped to a minimum of 0.05 and a maximum of 0.45, i.e. , and *α*_{L}=*α*_{R}=(1−2*α*_{0})/2. Observe that the capping means that *α*_{L} and *α*_{R} lie in the range [0.05,0.45] as well, thus satisfying the condition in theorem 2.3 requiring the *α*_{i}s to be constant. Then, the space used by the representation is bits. Provided capping is not applied, and because *n*_{0}=*n*_{2}+1 and *α*_{L}=*α*_{R}, this is easily seen to be *nH*(*x*)+*o*(*n*) bits, and is therefore bounded by *γn*+*o*(*n*) bits. If *x*>0.45, then the representation takes bits. Because , this is maximized with the least possible *n*_{0}=0.45*n*, where the space is precisely *nH*(0.45)+*o*(*n*)<*γn*+*o*(*n*). Similarly, for *x*<0.05, the space is less than *nH*(0.05)+*o*(*n*)<*γn*+*o*(*n*) bits.

We now explain how this data structure can answer RT2Qs in constant time. We use the data structure of theorem 2.3 constructed on *T*_{A} in order to find *u*=LCA(*i*,*j*)=RMQ(*i*,*j*). Subsequently,

We determine the start of

*M*_{u}within*M*by calculating .We locate the appropriate nodes from lispine(

*u*) and rispine(*u*) and the corresponding bits within*M*_{u}and make the required comparison.

We now explain each of these steps. For step (1), we use corollary 3.4. When evaluating the formula, we use the *O*(1)-time support for Ldepth(*u*) and Rdepth(*u*) given by the data structure of §2; there we explain how to compute Ldepth(*u*) in constant time (computing Rdepth(*u*) can be done analogously). This leaves only the computation of *l*_{u} and Lleaves(*u*). The former is done as follows. We check if *u* has a left child: if not, then *l*_{u}=0. Otherwise, if *v* is *u*’s left child, then *v* and *u*−1 are, respectively, the top-most and lowest nodes in lispine(*u*). We can then obtain *l*_{u} in *O*(1) time as depth(*v*)−depth(*u*) in *O*(1) time by theorem 2.3. On the other hand, Lleaves(*u*) can be computed as leaf-rank(*v*′+subtree-size(*v*′)−1),^{3} where *v*′=node-select_{inorder}(*v*) and *v* is the left child of *u*. If *v* does not exist then Lleaves(*u*)=leaf-rank(*u*′), where *u*′=node-select_{inorder}(*u*). All those operations take *O*(1) time by theorem 2.3.

For step (2), we use lemma 3.1 to locate the two candidates from *A*[*i*..*u*−1] and *A*[*u*+1..*j*] (assuming that *i*<*u*<*j*; if not, the problem is easier) in *O*(1) time as *v*=LCA(*i*,*u*−1) and *w*=LCA(*u*+1,*j*). Next, we obtain the rank *ρ*_{v} of *v* in lispine(*u*) in *O*(1) time as depth(*u*−1)−depth(*v*). The rank *ρ*_{w} of *w* in rispine(*u*) is obtained similarly. Now, letting , we compare select_{M}(0,rank_{M}(0,*Δ*)+*ρ*_{v}) and select_{M}(1,rank_{M}(1,*Δ*)+*ρ*_{w}) in *O*(1) time to determine which of *v* and *w* is smaller and return that as the answer to R2M(*i*,*j*).^{4} We have thus shown:

### Theorem 3.5

*Given an array of n elements from a totally ordered set, there exists a data structure of size at most γn+o(n) bits that supports RT2Qs in O(1) time, where* .

Note that *γn* is a worst-case bound. The size of the encoding can be less for other values of *n*_{0}. In particular, because *H*(*x*) is convex, and the average value of *n*_{0} on random permutations is *n*/3 [16], theorem 1, we have by Jensen’s inequality that the expected size of the encoding is below .

## 4. Effective entropy of the RT2Q and R2M problems

Here, we lower bound the effective entropy of the RT2Q problem, that is, the number of equivalence classes of arrays distinguishable by RT2Qs. For this sake, we define *extended* Cartesian trees, in which each node *v* indicates a merging order between its left and right internal spines, using a number in a universe of size (*l*_{v}+*r*_{v} *r*_{v}) . We prove that any distinct extended Cartesian tree can arise for some input array, and that any two distinct extended Cartesian trees give a different answer for at least some RT2Qs. Then, we aim to count the number of distinct extended Cartesian trees.

While unable to count the exact number of extended Cartesian trees, we provide a lower bound by unrolling their recurrence a finite number of times (precisely, up to eight levels). This effectively limits the lengths of internal spines we analyse, and gives us a number of configurations of the form (1/0.160646^{n})*θ*(*n*) for a polynomial *θ*(*n*), from where we obtain a lower bound of bits on the effective entropy of the RT2Q problem.

We note that our bound on RT2Qs also applies to the weaker R2M operation, because any encoding answering R2Ms has enough information to answer RT2Qs. Indeed, it is easy to see that RMQ(*i*,*j*) is the only position that is not the answer to any query R2M(*i*′,*j*′) for any *i*≤*i*′<*j*′≤*j*. Then, with RMQ and R2M, we have RT2Q. Therefore, we can give our result in terms of the weaker R2M.

### Theorem 4.1

*The effective entropy of the R2M (and the RT2Q) problem over an array A[1,n] is at least* .

### (a) Modelling the effective entropy of R2M

Recall that to show that the effective entropy of the RMQ problem is bits, we argue that (i) any two Cartesian trees give a different answer to at least one RMQ(*i*,*j*); (ii) any binary tree is the Cartesian tree of some permutation *A*[1,*n*]; (iii) the number of binary trees of *n* nodes is (1/*n*+1)(2*n* *n*) ; thus, in the worst case, one needs at least bits to distinguish among them.

A similar reasoning can be used to establish a lower bound on the effective entropy of the RT2Q problem. We consider an extended Cartesian tree *T* of size *n*, where for any node *v* having both left and right children, we store a number *M*(*v*) in the range [1..(*l*_{v}+*r*_{v} *r*_{v}) ]. The number *M*(*v*) identifies one particular merging order between the nodes in lispine(*v*) and rispine(*v*), and (*l*_{v}+*r*_{v} *r*_{v}) is the exact number of different merging orders we can have.

Now, we follow the same steps as before. For (i), let *T* and *T*′ be Cartesian trees extended with the corresponding numbers *M*(*v*) for *v*∈*T* and *M*′(*v*′) for *v*′∈*T*′. We already know that if the topologies of *T* and *T*′ differ, then there exists an RMQ(*i*,*j*) that gives different results on *T* and *T*′. Assume now that the topologies are the same, but there exists some node *v* where *M*(*v*) differs from *M*′(*v*). Then, there exists an RT2Q(*i*,*j*), where the extended trees give a different result. W.l.o.g., let *i* and *j* be the first positions of lispine(*v*) and rispine(*v*), respectively, where *v*_{l}=lispine(*v*)[*i*] goes before *v*_{r}=rispine(*v*)[*j*] according to *M*(*v*), but after according to *M*′(*v*). Then, *T* answers R2M(*v*_{1},*v*_{2})=*v*_{1} and *T*′ answers R2M(*v*_{1},*v*_{2})=*v*_{2} (we interpret *v*_{1} and *v*_{2} as inorder numbers here).

As for (ii), let *T* be an extended Cartesian tree, where *u* is the (inorder number of the) root of *T*. Then, we build a permutation *A*[1,*n*] whose extended tree is *T* as follows. First, we set the minimum at *A*[*u*]=0. Now, we recursively build the ranges *A*[1,*u*−1] (a permutation with values in [0..*u*−1]) and *A*[*u*+1,*n*] (a permutation with values in [0..*n*−*u*−1]) for the left and right child of *T*, respectively. Assume, inductively, that the permutations already satisfy the ordering given by the *M*(*v*) numbers for all the nodes *v* within the left and right children of *u*. Now, we are free to map the values of *A*∖*A*[*u*] to the interval [1,*n*−1] in any way that maintains the relative ordering within *A*[1,*u*−1] and *A*[*u*+1,*n*]. We do so in such a way that the elements of lispine(*u*) and rispine(*u*) compare according to *M*(*u*). This is always possible: we sort *A*[1,*u*−1] and *A*[*u*+1,*n*] from smallest to largest values, let *A*[*a*_{i}] be the *i*th smallest cell of *A*[1,*u*−1] and *A*[*b*_{j}] the *j*th smallest cell of *A*[*u*+1,*n*]. In addition, we set cursors at lispine(*u*)[*l*] and rispine(*u*)[*r*], initially *l*=*r*=1, and set *c*=*i*=*j*=1. At each step, if *M*(*u*) indicates that lispine(*u*)[*l*] comes before rispine(*u*)[*r*], we reassign *A*[*a*_{i}]=*c* and increase *i* and *c*, until (and including) the reassignment of *a*_{i}=lispine(*u*)[*l*], then we increase *l*; otherwise, we reassign *A*[*b*_{j}]=*c* and increase *j* and *c*, until (and including) the reassignment of *b*_{j}=(*u*)[*r*], then we increase *r*. We repeat the process until reassigning all the values in *A*∖*A*[*u*].

For (iii), next, we lower bound the total number of extended Cartesian trees.

### (b) Lower bound on effective entropy

As explained, we have been unable to come up with a general counting method for the lower bound, yet we give a method that can be extended with more and more effort to obtain better and better lower limits. The idea is to distinguish the first steps in the generation of the Cartesian tree out of the root node, and charge the minimum value for (*l*_{v}+*r*_{v} *r*_{v}) that we can ensure in each case. Let
where *t*(*n*) is the number of extended Cartesian trees with *n* nodes, counted using some simple lower-bounding technique. For example, if we consider the simplest model for *T*(*x*), then we have that a (non-empty) tree is a root *v* either with no children, with a left child rooting a tree, with a right child rooting a tree or with left and right children rooting trees, this time multiplied by 2 to account for (*l*_{v}+*r*_{v} *r*_{v}) ≥(2 1) (see levels 0 and 1 in figure 2). Then, *T*(*x*) satisfies
which solves to
which has two singularities at . The one closest to the origin is . Thus, it follows that *t*(*n*) is of the form for some polynomial *θ*(*n*) [20], and thus we need at least bits to represent all the possible extended Cartesian trees.

This result can be improved by unrolling the recurrence of *T* further, that is, replacing each *T* by its four possible alternatives in the basic definition. Then, the lower bound improves, because some left and right internal spines can be seen to have length two or more. The results do not admit easy algebraic solutions anymore, but we can numerically analyse the resulting functions with Maple and establish a safe numeric threshold from where higher lower bounds can be derived. For example, by doing a first level of replacement in the simple recurrence, we obtain a recurrence with 25 cases, which yields
(see level 2 in figure 2) which Maple is able to solve algebraically, although the formula is too long to display it here. While Maple could not algebraically find the singularities of *T*(*x*), we analysed the result numerically and found a singularity at *x*=0.190879… Therefore, we conclude that *t*(*n*)≥(1/0.190880^{n})*θ*(*n*), and thus that a lower bound is .

To find the singularity, we used the result [21], theorem VII.3 that, under certain conditions that are met in our case, the singularities of an equation of the form *T*(*x*)=*G*(*x*,*T*(*x*)) can be found by numerically solving the system formed by the equation *T*=*G*(*x*,*T*) and its derivative, 1=∂*G*(*x*,*T*)/∂*T*. If the positive solution is found at (*x*=*r*, *T*=*γ*), then there is a singularity at *x*=*r*. If, further, *T*(*x*) is aperiodic (as in our case), then *r* is the unique dominant singularity and *t*(*n*)=(1/*r*^{n})*θ*(*n*) for some polynomial *θ*(*n*).

To carry the idea further, we wrote a program that generates all the combinations of any desired level, and builds a recurrence to feed Maple with. We use the program to generate the recurrences of level 3 onwards. Table 1 shows the results obtained up to level 8, which is the one yielding the lower bound of theorem 4.1. This was not without challenges; we describe the details in appendix A.

## 5. Conclusion

We obtained a succinct binary tree representation that extends the representation of Farzan & Munro [3] by supporting navigation based on the inorder numbering of the nodes, and a few additional operations. Using this representation, we describe how to encode an array in optimal space in a more natural way than the existing structures, to support RMQs in constant time. In addition, this representation reaches 1.919*n*+*o*(*n*) bits on random permutations, thus breaking the worst-case lower bound of bits. This is not known to hold on any alternative representation. It is an open question to find a data structure that answers RMQs in *O*(1) time using 2*n*+*o*(*n*) bits in the worst case, while also achieving the expected effective entropy bound of about 1.736*n* bits for random arrays *A*.

Then, we obtain another structure that encodes an array of *n* elements from a total order using 3.272*n*+*o*(*n*) bits to support RT2Qs in *O*(1) time. This uses almost half of the 6*n*+*o*(*n*) bits used for this problem in the literature [8]. Our structure can possibly be plugged into their solution, thus reducing their space.

While the effective entropy of the RMQ problem is known to be precisely bits, the effective entropy for range top-*k* queries is only known asymptotically: it is at least bits, and at most bits [8]. We have shown that, for *k*=2, the effective entropy is at least bits. Determining the precise effective entropy for *k*≥2 is an open question.

## Funding statement

P.D. is supported by NSF grant CCF-1018370 and BSF grant 2010437 (work partially done while P.D. was with MADALGO, Center for Massive Data Algorithmics, a Center of the Danish National Research Foundation, grant DNRF84, Aarhus University, Denmark). G.N. was partially funded by Millennium Nucleus Information and Coordination in Networks ICM/FIC P10-024F, Chile. S.S.R. is partly supported by the Basic Science Research Programme through the National Research Foundation of Korea supported by the Ministry of Education, Science and Technology (grant no. 2012-0008241).

## Acknowledgements

Many thanks to Jorge Olivos and Patricio Poblete for discussions (lectures) on extracting asymptotics from generating functions.

## Appendix A. Unrolling the lower bound recurrence

The main issue to unroll further levels of the recurrence is that it grows very fast. The largest tree at level ℓ has 2^{ℓ} leaves labelled *T*. Each such leaf is expanded in four possible ways to obtain the trees of the next level. Let *A*(ℓ) be the number of trees generated at level ℓ. If all the *A*(ℓ−1) trees had 2^{ℓ−1} leaves labelled *T*, then we would have *A*(ℓ)=*A*(ℓ−1)⋅4^{2ℓ−1}≤2^{2ℓ+1}. If we consider just one tree of level ℓ with 2^{ℓ} leaves labelled *T*, we have *A*(ℓ)=4^{2ℓ−1}=2^{2ℓ}. Thus, the number of trees to generate is 2^{2ℓ}≤*A*(ℓ)≤2^{2ℓ+1}. For levels 3 and 4, we could just generate and add up all the trees, but from level 5 onwards we switched to a dynamic programing-based counting that performs *O*(ℓ^{4}⋅16^{ℓ}) operations, which completed level 5 in 40 s instead of 4 days of the basic method. It also completed level 6 in 20 min, level 7 in 10 h and level 8 in 10 days. We had to use unbounded integers,^{5} because 64-bit numbers overflow already in level 5 and their width doubles every new level. Apart from this, the degree of the generated polynomials doubles at every new level and the number of terms grows by a factor of up to 4, putting more pressure on Maple. In level 3, with polynomials of degree 8, Maple is already unable to algebraically solve the equations related to *G*(*x*,*T*), but they can still be solved numerically. From level 5 onwards, Maple was unable to solve the system of two equations, and we had to find the singularity by plotting the implicit function and inspecting the axis *x*∈[−1,1].^{6} From level 6 onwards, Maple could not even plot the implicit function, and we had to manually find the solution of the two equations on *G*(*x*,*T*). At this point, even loading the equation into Maple is troublesome; for example, in level 7, we had to split the polynomial into 45 chunks to avoid causing Maple to crash, and in level 8, we used 100 chunks.

Level 9 is expected to take about 1 year, and in addition we cannot compile, as we reach an internal limit of the library to handle large integers: the space usage of the dynamic programing tables grows as *O*(ℓ^{2}⋅4^{ℓ}) and, for level 9, it surpasses 2^{30} large integers. Thus, we are very close to reaching various limits of practical applicability of this technique. A radically different model is necessary to account for every possible internal spine length and thus obtain the exact lower bound.

## Footnotes

One contribution of 11 to a Theo Murphy Meeting Issue ‘Storage and indexing of massive data’.

An extended abstract of some of the results in §§1 and 2 appeared in

*Computing and Combinatorics: Proceedings of the 18th Annual International Conference COCOON 2012, Sydney, Australia, 20–22 August 2012*(eds J Gudmundsson, J Mestre, T Viglas), pp. 396–407. Lecture Notes in Computer Science, vol. 7434. Berlin, Germany: Springer.↵1 The time complexity of this result assumes the word RAM model with logarithmic word size, as do all subsequent results in this paper.

↵2 This list includes left-child(

*v*), right-child(*v*), parent(*v*), child-rank(*v*), degree(*v*), subtree-size(*v*), depth(*v*), height(*v*), left-most-leaf(*v*), right-most-leaf(*v*), leaf-rank(*v*), leaf-select(*j*), level-ancestor(*v*,*i*), LCA(*u*,*v*), distance(*u*,*v*), level-right-most(*i*), level-left-most(*i*), level-successor(*v*) and level-predecessor(*v*), where*v*denotes a node,*i*denotes a level, and*j*is an integer. Refer to the original articles [12,3] for the definition of these operations.↵3 Leaf-rank(

*u*) denotes the number of leaves that appear before*u*in the pre-order traversal for any pre-order number*u*.↵4 If we select the last (non-represented) bit of

*M*_{u}, the result will be out of the*M*_{u}area of*M*, but nevertheless the result of the comparison will be correct.↵5 With the GNU Multiple Precision Arithmetic Library (GMP), at http://gmplib.org.

↵6 Note that, in principle, there is a (remote) chance of us missing the dominant singularity by visual inspection, finding one further from the origin instead. Even in this case, each singularity implies a corresponding exponential term in the growth of the function, and thus we would find a valid lower bound.

- © 2014 The Author(s) Published by the Royal Society. All rights reserved.