Faculty of Computer Science, Dalhousie University,
<EMAIL_ADDRESS>of Computer Science, Dalhousie University,
<EMAIL_ADDRESS>Department of Computer Science, Michigan Technological
University<EMAIL_ADDRESS>Younan Gao, Meng He and Yakov
Nekrich [500]Theory of computation Computational geometry [500]Theory of
computation Data structures design and analysis REMOVED

# Fast Preprocessing for Optimal Orthogonal Range Reporting and Range
Successor with Applications to Text Indexing

Younan Gao  Meng He  Yakov Nekrich

###### Abstract

Under the word RAM model, we design three data structures that can be
constructed in $O(n\sqrt{\lg n})$ time over $n$ points in an $n\times n$ grid.
The first data structure is an $O(n\lg^{\epsilon}n)$-word structure supporting
orthogonal range reporting in $O(\lg\lg n+k)$ time, where $k$ denotes output
size and $\epsilon$ is an arbitrarily small constant. The second is an
$O(n\lg\lg n)$-word structure supporting orthogonal range successor in
$O(\lg\lg n)$ time, while the third is an $O(n\lg^{\epsilon}n)$-word structure
supporting sorted range reporting in $O(\lg\lg n+k)$ time. The query times of
these data structures are optimal when the space costs must be within
$O(n\operatorname{polylog}n)$ words. Their exact space bounds match those of
the best known results achieving the same query times, and the $O(n\sqrt{\lg
n})$ construction time beats the previous bounds on preprocessing. Previously,
among 2d range search structures, only the orthogonal range counting structure
of Chan and Pǎtraşcu (SODA 2010) and the linear space, $O(\lg^{\epsilon}n)$
query time structure for orthogonal range successor by Belazzougui and Puglisi
(SODA 2016) can be built in the same $O(n\sqrt{\lg n})$ time. Hence our work
is the first that achieve the same preprocessing time for optimal orthogonal
range reporting and range successor. We also apply our results to improve the
construction time of text indexes.

###### keywords:

orthogonal Range search, geometric data structures, orthogonal range
reporting, orthogonal range successor, sorted range reporting, text indexing,
word RAM

###### category:

##  1 Introduction

Two dimensional orthogonal range search problems have been studied intensively
in the communities of computational geometry, data structures and databases.
The goal of these problems is to maintain a set, $N$, of points on the plane
in a data structure such that one can efficiently compute aggregate
information about the points contained in an axis-aligned query rectangle $Q$.
Among these problems, orthogonal range counting and orthogonal range reporting
are perhaps the most fundamental; the former counts the number of points
contained in $N\cap Q$ while the latter reports them. Another well-known
problem is orthogonal range successor, which asks for the point in $N\cap Q$
with the smallest $x$\- or $y$-coordinate. Range counting, reporting and
successor have many applications including text indexing [24, 9, 7, 26],
Lempel-Ziv decomposition [5] and consensus trees in phylogenetics [20], to
name a few. See [23] for a survey on the connection between text indexing and
various range searching techniques.

Most work on orthogonal range search [13, 19, 11, 28, 32] focuses on achieving
the best tradeoffs between query time and space, and preprocessing time is
often neglected. However, the preprocessing time of a data structure matters
when it is used as a building block of an algorithm processing plain data, as
the total running time includes that needed to build the structure.
Furthermore, an orthogonal range search structures with fast construction time
are preferred when preprocessing huge amounts of data, e.g., when used as
components of text indexes built upon large data sets from search engines and
bioinformatics applications. The work of Chan and Pǎtraşcu [12] is the first
that breaks the $O(n\lg n)$ bound on the construction time of 2d orthogonal
range counting structures; they designed an $O(n)$-word structure with $O({\lg
n}/{\lg\lg n})$ query time that can be built in $O(n\sqrt{\lg n})$ time. Their
ideas were further extended to design an $O(n{\lg\sigma}/{\sqrt{\lg n}})$-time
algorithm to build an binary wavelet trees over a string of length $n$ drawn
from $[\sigma]$ [27, 3]111In this paper, $\sigma$ denotes
$\\{0,1,\ldots,\sigma-1\\}$., which is a key data structure used in succinct
text indexes. More recently, Belazzougui and Puglisi [5] showed how to
construct an $O(n)$-word data structure in $O(n\sqrt{\lg n})$ time to support
range successor in $O(\lg^{\epsilon}n)$ time, and applied it to achieve new
results on Lempel-Ziv parsing.

The previous work on constructing orthogonal range search structures in
$O(n\sqrt{\lg n})$ time focuses on linear space data structure. To achieve
optimal query time for 2d orthogonal range reporting and range successor using
near-linear space, however, the best tradeoffs under the word RAM model
requires superlinear space [11, 32]. The increased space costs are needed to
encode more information, posing new challenges to fast construction. We thus
investigate the problem of designing data structures with optimal query times
for range reporting and range successor that can be built in $O(n\sqrt{\lg
n})$ time, while matching the space costs of the best known solutions. We also
consider a closely related problem called sorted range reporting [28] to
achieve similar goals. In this problem, we report all points in $N\cap Q$ in a
sorted order along either $x$\- or $y$-axis. The query time should depend on
the number of points actually reported even if the procedure is ended early by
user.

##### Previous Work.

The research on 2d orthogonal range reporting has a long history [13, 2, 19,
11]. Researchers have achieved three best tradeoffs between query time and
space costs under the word RAM model; we follow the state of the art and
assume that the input points are in rank space. The solution with optimal
query time of $O(\lg\lg n+k)$ and space cost of $O(n\lg^{\epsilon}n)$ words is
due to Alstrup et al. [2], while the best linear-space solution is designed by
Chan et al [11] which answers a query in $O((1+k)\lg^{\epsilon}n)$ time, where
$k$ is the output size and $\epsilon$ is an arbitrarily small constant. Chan
et al. also proposed an $O(\lg\lg n)$-word structure with $O((1+k)\lg\lg n)$
query time and another tradeoff matching that of Alstrup et al. [2].

The 2d orthogonal range successor problem has also been well studied. After a
series of work [22, 21, 15, 14, 31], Nekrich and Navarro [28] gave two
solutions to this problem; the first uses $O(n)$ words and answers a query in
$O(\lg^{\epsilon}n)$ time, while the second uses $O(n\lg\lg n)$ words to
answer a query in $O((\lg\lg n)^{2})$ time. Zhou [32] decreased the query time
of the latter to $O(\lg\lg n)$ without increasing space costs. By definition,
a solution to orthogonal range successor implies that to sorted range
reporting. Furthermore, Nekrich and Navarro [28] also designed a data
structure using $O(n\lg^{\epsilon}n)$ words to support sorted range reporting
in $O(\lg\lg n+k)$ time. Hence, the best three time-space tradeoffs for the
original 2d orthogonal range reporting problem has also been achieved for the
sorted version. The optimality of the $O(\lg\lg n+k)$ query time for
orthogonal range reporting and the $O(\lg\lg n)$ query time for orthogonal
range successor when no more than $O(n\operatorname{polylog}n)$ space can be
used is established by a lower bound on range emptiness [29].

Alstrup et al. [2] claimed that their structure for optimal orthogonal range
reporting can be constructed in $O(n\lg n)$ expected time. Even though
preprocessing times are not given in [11, 28, 32], straightforward analyses
reveal that the other data structures we surveyed here can be built in $O(n\lg
n)$ worst-case time (Bille and Gørtz [7] also claimed that the preprocessing
time of the $O(n\lg\lg n)$-word structure of Chan et al. [11] is $O(n\lg n)$).
Hence, when faster preprocessing time is needed in their solution to Lempel-
Ziv decomposition, Belazzougui and Puglisi [5] had to design a new linear-
space data structure for orthogonal range successor with $O(n\sqrt{\lg n})$
preprocessing time and $O(\lg^{\epsilon}n)$ query time. No attempts have been
published to achieve similar preprocessing times for other tradeoffs.

##### Our Results.

Under the word RAM model, we design the following three data structures that
can be constructed in $O(n\sqrt{\lg n})$ time over $n$ points in an $n\times
n$ grid:

  * •

An $O(n\lg^{\epsilon}n)$-word structure supporting orthogonal range reporting
in $O(\lg\lg n+k)$ time, where $k$ denotes output size and $\epsilon$ is an
arbitrarily small constant;

  * •

An $O(n\lg\lg n)$-word structure supporting orthogonal range successor in
$O(\lg\lg n)$ time;

  * •

An $O(n\lg^{\epsilon}n)$-word structure supporting sorted range reporting in
$O(\lg\lg n+k)$ time.

The query times of these structures are optimal when space costs must be
within $O(n\operatorname{polylog}n)$ words. Their exact space bounds match
those of the best known results achieving the same query times, and the
$O(n\sqrt{\lg n})$ construction time beats the previous bounds on
preprocessing. Note that even though our third result implies the first, our
data structure for the first is much simpler. In addition, our results can be
used to improve the construction time of text indexes. For a text string $T$
of length $n$ over alphabet $[\sigma]$, we design

  * •

A text index of $O(n\lg\sigma\lg^{\epsilon}n)$ bits that can be constructed in
$O(n\lg\sigma/\sqrt{\lg n})$ time and can report the $\mathtt{occ}$
occurrences of a pattern of length $p$ in time
$O({p}/{\log_{\sigma}n}+\log_{\sigma}n\lg\lg n+\mathtt{occ})$, where
$\epsilon$ is any small positive constant. This improves one result of Munro
et al. [26] who designed the first text indexes with both sublinear
construction time and query time for small $\sigma$; for the same time-space
tradeoff, their preprocessing time is $O(n\lg\sigma\lg^{\epsilon}n)$.

  * •

A text index of $O(n\lg^{1+\epsilon}n)$ bits for any constant $\epsilon>0$
built in $O(n\sqrt{\lg n})$ time that supports position-restricted substring
search [24] in $O({p}/{\log_{\sigma}n}+\lg p+\lg\lg\sigma+\mathtt{occ})$ time.
Previous indexes with similar query performance require $O(n\lg n)$
construction time.

##### Overview of Our Approach.

We first discuss why some obvious approaches will not work. The modern
approach of Chan et al [11] for orthogonal range reporting is based on a
problem called ball inheritance which they defined over range trees. This
solution is well-known for its simplicity, and by choosing different
parameters in their approach to ball inheritance, they obtain all three best
known tradeoffs. One natural idea is to redesign the structures stored at
range tree nodes to use bit packing to speed up construction. However, even
though we have achieved construction time matching the state of the art for
these structures, it is still not enough to construct the data structures for
the tradeoffs of ball inheritance that we need quickly enough. Another idea is
to tune the parameters in the approach of Belazzougui and Puglisi [5], hoping
to obtain the tradeoffs that we aim for, as they already showed how to
construct in $O(n\sqrt{\lg n})$ time a linear space, $O((k+1)\lg^{\epsilon}n)$
query time structure for orthogonal range reporting. Their solution uses many
trees grouped into $O(\lg^{\epsilon}n)$ levels of granularity. If we borrow
ideas from [11] to set parameters to achieve different tradeoffs, we would use
$O(1/\epsilon)$ or $O(\lg\lg n)$ levels of granularity. However, to return a
point in the answer, their query algorithm would perform operations requiring
$O(\lg\lg n)$ time at each level of granularity. Thus, at best, the former
would give an $O(n\lg^{\epsilon}n)$-word structure with $O((k+1)\lg\lg n)$
query time and the latter an $O(n\lg\lg n)$-word structure with
$O((k+1)(\lg\lg n)^{2})$ query time. Either solution is inferior to best known
tradeoffs. This however is fine in the original solution, as the total cost of
spending $O(\lg\lg n)$ time at each of the $O(\lg^{\epsilon}n)$ levels is
bounded by $O(\lg^{\epsilon^{\prime}}n)$ for any $\epsilon^{\prime}>\epsilon$.

We thus design new approaches. For optimal orthogonal range reporting, our
overall strategy is to perform two levels of reductions, making it sufficient
to solve ball inheritance in special cases with fast preprocessing time. More
specifically, we first use a generalized wavelet tree and range
minimum/maximum structures to reduce the problem in the general case to the
special case in which the points are from a $2^{\sqrt{\lg n}}\times
n^{\prime}$ (narrow) grid, where $n^{\prime}\leq n$. In this reduction, we
need only support ball inheritance over a wavelet tree with high fanout. We
further reduce the problem over points in a narrow grid to that over a (small)
grid of size at most $2^{\sqrt{\lg n}}\times 2^{2\sqrt{\lg n}}$. This is done
by grouping points and selecting representatives from each group, so that
previous results with slower preprocessing can be used over the smaller set of
representatives. Finally, over the small grid, we solve ball inheritance when
the coordinates of each point can be encoded in $O(\sqrt{\lg n})$ bits. The
ball inheritance structures in both special cases can be built quickly by
redesigning components with fast preprocessing, though the second case
requires a twist to the approach of Chan et al [11]. Our solutions to optimal
range successor and sorted range reporting are based on similar strategies,
though we preform more levels of reductions.

In the main body of this paper, we describe our data structures for optimal
range reporting and successor, while leaving those for optimal sorted range
reporting in Appendix G.

##  2 Preliminaries

In this section, we describe and sometimes extend the previous results used in
this paper. The proofs omitted from this section can be found in Appendix A.

##### Notation.

We adopt the word RAM model with word size $w=\Theta(\lg n)$ bits, where $n$
often denotes the size of the given data. Our complete solutions use several
sets of homogeneous components. We present a lemma to bound the costs of each
different type of components, which is then applied over the entire set of
these components to calculate the total cost. The size, $n^{\prime}$, of the
data that each component represents may be less than $n$ which is the input
size of the entire problem, so when the cost of constructing the component is
bounded by a function of the form $f(n^{\prime})/\operatorname{polylog}(n)$ to
take advantage of the word size, we keep both $n^{\prime}$ and $n$ in the
lemma statement, as commonly done in previous work on similar topics. In this
case, the construction algorithm usually uses a universal table of $o(n)$
bits, whose content solely depends on the value of $n$, and hence can be
constructed once in $o(n)$ time and used for all data structure components of
the same type. Thus unless otherwise stated, these lemmas assume the existence
of such a table without stating so explicitly in the lemma statements, and we
define and analyze the table in the proof. This also applies to algorithms
that manipulates sequences of size $n^{\prime}$. Occasionally the query
algorithms of a data structure may need a universal table as well, and we
explicitly state it if this is the case.

We say a sequence $A\in[\sigma]^{n}$ is in $packed$ form if the bits of its
elements are concatenated and stored in as few words as possible. Thus, when
packed, $A$ occupies $\lceil n\lceil{\lg\sigma}\rceil/w\rceil$ words.

Under the word RAM model with word size $w=\Theta(\lg n)$, $O(\lg
n/\lg\sigma)$ integers from $[\sigma]$ can be packed in one word. Using the
well-known approach of simulating external memory algorithms under word RAM
[w2014], the following algorithm for sorting packed sequences follows directly
from external sorting:

######  Lemma 2.1.

A packed sequence $A[0..n^{\prime}-1]$ from alphabet $[\sigma]$, where
$max(\sigma,n^{\prime})\leq n$, can be sorted in $O(n^{\prime}\lg
n^{\prime}{\lg\sigma}/{\lg n})$ time with the help of a universal tables of
$o(n)$ bits.

Next, we show a fast and stable sorting algorithm over a packed sequence of
small integers:

######  Lemma 2.2.

Let $A[0..n^{\prime}-1]$ be a packed sequence drawn from alphabet $[\sigma]$,
where $max(\sigma,n^{\prime})\leq n$. Let $\psi$ denote the number of distinct
symbols in $A$ where $\psi\leq n^{\prime}$. There is an algorithm to stably
sort $n^{\prime}$ elements in $A$ in $O(n^{\prime}({\lg\sigma})(\lg\psi)/{\lg
n})$ time with the help of a universal tables $o(n)$ bits. The sorting
algorithm uses $n^{\prime}\lg\sigma$ bits of working space.

######  Proof 2.3.

The sorting algorithm is the same as creating a balanced binary tree $T$. We
sort part of elements in $A$ at each tree level. Eventually, all elements are
sorted at the leaf level. Let $r$ denote the root node. We create the sequence
$A(r)=A$. Among the $n^{\prime}$ elements encoded with $\lg\sigma$ bits each,
we find the length $\gamma$ of the common most significant bits. If $\gamma$
is equal to $\lg\sigma$, it means all elements in $A(r)$ are the same, we stop
classifying elements in the next level and make it as a leaf node. Otherwise,
we create the left child, $r_{0}$, and the right child, $r_{1}$, of $r$, and
perform a linear scan of $A(r)$. During the scan, for each $i\in[0,|A(r)|-1]$,
if the $(\gamma+1)$-th bit of the binary representation of $A(r)[i]$ is 0 or
1, $A(r)[i]$ is appended to into $A(r_{0})$ or $A(r_{1})$, respectively.
Afterwards, we discard the sequence $A(r)$ and recursively process the child
node $r_{0}$ and $r_{1}$ in the same manner. In general, when generating the
sequences for the child nodes of an internal node $u$, we find the length
$\gamma$ of the common most significant bits among the binary expression of
elements of $A(u)$. If $\gamma$ is equal to $\lg\sigma$, we make $u$ as a leaf
node. Otherwise, for each $i\in[0,|A(u)|-1]$, if the $(\gamma+1)$-th bit of
the binary representation of $A(u)[i]$ is 0 or 1, $A(u)[i]$ is appended to
$A(u_{0})$ or $A(u_{1})$, respectively.

To speed up this process, we use a universal table $U$. Let
$b=\lfloor\frac{\lg n}{2\lg\sigma}\rfloor$ denoting the block size. For a
packed sequence $\hat{S}$ of any possible $b$-element drawn from $[\sigma]$,
$U$ stores an answer encoded with $\lg\lg\sigma$ bits denoting the length of
the common significant bits among elements of $\hat{S}$. As there are
$2^{b\times\lg\sigma}\leq\sqrt{n}$ entries in $U$ and each entry stores a
result of $\lg\lg\sigma$ bits, $U$ occupies
$O(\sqrt{n}\times\lg\lg\sigma)=o(n)$ bits of space. By performing table
lookups with $U$, we can retrieve the length of the common significant bits
among elements of a sequence $A(u)$ in $O(|A(u)|/b+1)=O(|A(u)|\lg\sigma/\lg
n+1)$ time. In addition, we need another universal table $U^{\prime}$ of
$o(n)$ bits (similar to the table $U$ in the proof of Lemma 2.4) to divide a
packed sequence of any possible $b$ elements into two packed subsequences
according to the bit value of each element at a given position $\gamma$, where
$\gamma\in[0,\lg\sigma-1]$. With $U$ and $U^{\prime}$, generating the
sequences for the child nodes of an internal node $u$ can be processed in
$O(|A(u)|\lg\sigma/\lg n+1)$ time. As $A[0,n^{\prime}-1]$ has $\psi$ distinct
elements, the tree $T$ would have as many as $\psi$ nodes and there are at
least $\psi$ sequences to be generated. Hence, the sorting algorithm would
take $\Omega(\psi)$ time. However, $\psi$ could be as large as $n^{\prime}$,
which is too expensive to afford. Thus, we modify the structure of $T$ to
decrease the $\Omega(\psi)$ term. We add one more condition when making a node
as a leaf: If $|A(u)|$ at node $u$ are $\leq b$, we make $u$ as a leaf node.
The modification would bring two following properties. First, if a leaf
sequence $|A(l)|$ satisfies $|A(l)|>b$, then all elements of $A(l)$ share the
same symbol. In this case, we do not need to sort elements in $A(l)$. Second,
as there are at most $\lceil n^{\prime}/b\rceil$ nodes at each level, the
sorting algorithm generates in total
$O(n^{\prime}/b\times\lg\psi)=O(n^{\prime}\lg\sigma/\lg n\times\lg\psi)$ leaf
sequences. For each of $O(\frac{n^{\prime}}{b}\times\lg\psi)$ leaf sequences
$A(l)$, if $|A(l)|\leq b$, we can apply a universal table $U^{\prime\prime}$
of $o(n)$ bits to sort them in constant time. Otherwise, all elements in
$A(l)$ are the same and sorting is unnecessary. $U^{\prime\prime}$ has an
entry for each possible pair $(E,c)$, where $E$ is a sequence of length $b$
drawn from universe $[\sigma]$ and $c$ is an integer in $[0,b]$. This entry
stores a packed sequence of the leftmost $c$ elements of $E$ in a sorted order
occupying $c\lg\sigma$ bits of space. Similar to $U$, $U^{\prime\prime}$ uses
$o(n)$ bits of space. After generating all leaf sequences, we linearly scan
each of them. If a leaf sequence $A(l)$ satisfies $|A(l)|\leq b$, we sort them
in constant time with $U^{\prime\prime}$. At last, we merge all the sorted
leaf sequences into one packed sequence.

At each node $u$, we spend $O(|A(u)|\lg\sigma/\lg n+1)$ time on processing.
The sum of the lengths of all the elements in the sequences at the same level
is at most $n^{\prime}$. As at most $\lg\psi$ levels and at most
$O(n^{\prime}\lg\sigma/\lg n\times\lg\psi)$ sequences are constructed, the
time required to construct the leaf sequences is
$\sum_{u}O(|A(u)|\lg\sigma/\lg n+1)=O(n^{\prime}\lg\sigma/\lg
n\times\lg\psi)$. Finally, sorting each leaf sequence and merge all of them
into one sequence takes another $O(n^{\prime}\lg\sigma/\lg n\times\lg\psi)$
time. Overall, the query algorithm takes
$O(n^{\prime}({\lg\sigma})(\lg\psi)/{\lg n})$ time.

##### Generalized Wavelet Trees.

Given a sequence $A[0..n-1]$ drawn from alphabet $[\sigma]$, a $d$-ary
generalized wavelet tree [25] $T_{d}$ over $A$ is a balanced tree in which
each internal node has $d$ children, where $2\leq d\leq\sigma$. For
simplicity, assume that $\sigma$ is a power of $d$. Each node of $T_{d}$ then
represents a range of alphabet symbols defined as follows: At the leaf level,
the $i$-th leaf from left represents the integer range $[i,i]$ for each
$i\in[0..\sigma-1]$. The range represented by an internal node is the union of
the ranges represented by its children. Hence the root represents
$[0,\sigma-1]$, and $T_{d}$ is a complete tree having $\log_{d}\sigma+1$
levels. Each node $u$ is further associated with a subsequence, $A(u)$, of
$A$, in which $A(u)[i]$ stores the $i$-th entry in $A$ that is in the range
represented by $u$. Thus the root is associated with the entire sequence $A$.
To save storage, $A[u]$ is not stored explicitly in [25]. Instead, each
internal node $u$ stores a sequence $S(u)$ of integers in $[d]$, where
$S(u)[i]=j$ if $A(u)[i]$ is within the range represented by the $j$th child of
$u$. All the $S(u)$’s built for internal nodes occupy $O(n\lg\sigma)$ bits in
total.

Generalized wavelet trees share fundamental ideas with range trees but are
more suitable for compact data structures over sequences which may contain
duplicate values. When we use them in this paper, we sometimes explicitly
store $A(u)$ for each node $u$, and may even associate with $u$ an additional
array $I(u)$ in which $I(u)[i]$ stores the index of $A(u)[i]$ in the original
sequence $A$. We call $A(u)$ the value array of $u$, and $I(u)$ the index
array. In this paper, if we construct value and/or index arrays for each node,
we explicitly state so. If not, it implies that we build a wavelet tree in
which each node $u$ is associated with $S(u)$ only. Furthermore, unless
otherwise specified, we apply the standard pointer-based implementation to
represent the tree structure of a wavelet tree, which is preprocessed in time
linear to the number of tree nodes such that the lowest common ancestor of any
two nodes can be located in $O(1)$ time [6]. We also number the levels of the
tree incrementally starting from the root level, which is level $0$. We have
the following two lemmas on constructing wavelet trees:

######  Lemma 2.4.

Let $A[0..n^{\prime}-1]$ be a packed sequence drawn from alphabet $[\sigma]$
and $I[0..n^{\prime}-1]$ be a packed sequence in which $I[i]=i$ for each
$i\in[0..n^{\prime}-1]$, where $n^{\prime}\leq n$ and $\sigma\leq
2^{O(\sqrt{\lg n})}$. Given $A$ and $I$ as input, a $d$-ary wavelet tree over
$A$ with value and index arrays in packed form can be constructed in
$O(n^{\prime}\lg\sigma(\lg n^{\prime}+\lg\sigma)/{\lg n}+\sigma)$ time, where
$d$ is an arbitrary power of $2$ with $2\leq d\leq\sigma$. If index arrays are
not constructed, the construction time can be lowered to
$O(n^{\prime}\lg^{2}\sigma/{\lg n}+\sigma)$; this bound still applies when
neither value nor index arrays are built.

######  Lemma 2.5.

Let $A[0..n-1]$ be a sequence drawn from alphabet $[\sigma]$. A $d$-ary
wavelet tree over $A$ with value and index arrays can be built in
$O({n\lg\sigma}/{\lg d})$ time where $2\leq d\leq\sigma$.

A sequence $A[0..n-1]$ drawn from $[\sigma]$ can be viewed as a point set
$N=\\{(A[i],i)|0\leq i\leq n-1\\}$. Let $T$ be a $d$-ary wavelet tree
constructed over $A$. Then ball inheritance [11] can be defined over $T$ which
asks for the support of these operations: i) $\mathtt{point}(v,i)$, which
returns the point $(A(v)[i],I(v)[i])$ in $N$ for an arbitrary node $v$ in $T$
and an integer $i$; and ii) $\mathtt{noderange}(c,d,v)$, which, given a range
$[c,d]$ and a node $v$ of $T$, finds the range $[c_{v},d_{v}]$ such that
$I(v)[i]\in[c,d]$ iff $i\in[c_{v},d_{v}]$. If we store the value and index
arrays explicitly, it is trivial to support these operations, but the space
cost is high. To save space, we only store $S(v)$ for each node $v$ and design
auxiliary structures. The following lemma presents previous results:

######  Lemma 2.6 ([11, Theorem 2.1], [10, Lemma 2.3]).

A generalized wavelet tree over a sequence $A[0..n-1]$ drawn from $[\sigma]$
can be augmented with ball inheritance data structure in $O(n\lg nf(\sigma))$
bits to support $\mathtt{point}$ in $O(g(\sigma))$ time and
$\mathtt{noderange}$ in $O(g(\sigma)+\lg\lg n)$ time, where (a)
$f(\sigma)=O(1)$ and $g(\sigma)=O(\lg^{\epsilon}\sigma)$; (b)
$f(\sigma)=O(\lg\lg\sigma)$ and $g(\sigma)=O(\lg\lg\sigma)$; or (c)
$f(\sigma)=O(\lg^{\epsilon}\sigma)$ and $g(\sigma)=O(1)$.

##### Data Structures for $\mathtt{rank}$ and $\mathtt{select}$.

Given a sequence $A$ drawn from alphabet $[\sigma]$, a
$\mathtt{rank}_{c}(A,i)$ operation computes the number of elements equal to
$c$ in $A[0..i]$, where $c\in[\sigma]$, while a $\mathtt{select}_{c}(A,i)$
returns the index of the entry of $A$ containing the $i$-th occurrence of $c$.
We have the following two lemmas on building $\mathtt{rank}$/$\mathtt{select}$
structures.

######  Lemma 2.7.

Let $A[0..n^{\prime}-1]$ be a packed sequence drawn from alphabet $[\sigma]$,
where $n^{\prime}\leq n$ and $\sigma=O(\operatorname{polylog}n)$. A data
structure of $n^{\prime}\lceil\lg\sigma\rceil+o(n^{\prime}\lg\sigma)$ bits
supporting $\mathtt{rank}$ in $O(1)$ time can be constructed in
$O(n^{\prime}\lg^{2}\sigma/\lg n+\sigma)$ time.

######  Lemma 2.8 ([3, Lemma 2.1]).

Given a packed bit sequence $B[0..n-1]$, a systematic data structure occupying
$o(n)$ extra bits can be constructed in $O(n/\lg n)$ time, which supports
$\mathtt{rank}$ and $\mathtt{select}$ in constant time.

In the above lemma, a data structure is systematic if it requires the input
data to be stored verbatim along with the additional information for answering
queries. A restricted version of $\mathtt{rank}$ is called partial rank; a
partial rank operation, $\mathtt{rank^{\prime}}(A,i)$, computes the number of
elements equal to $A[j]$ in $A[0..j]$. The following lemma presents a solution
to supporting $\mathtt{rank^{\prime}}$, which is an easy extension of [4,
Lemma 3.5].

######  Lemma 2.9.

Given a sequence $A[0..n-1]$ drawn from alphabet $[\sigma]$, a data structure
of $O(n\lg\sigma)$ bits can be constructed in $O(n+\sigma)$ time, which
supports $\mathtt{rank^{\prime}}$ in constant time.

##### Range Minimum/Maximum.

Given a sequence $A$ of $n$ integers, a range minimum/maximum query
$\mathtt{rmq}(i,j)/\mathtt{rMq}(i,j)$ with $i\leq j$ returns the position of a
minimum/maximum element in the subsequence $A[i..j]$. Fischer and Heun [16]
considered this problem:

######  Lemma 2.10 ([16]).

Given an array $A$ of $n$ integers, a data structure of $O(n)$ bits can be
constructed in $O(n)$ time, which answers $\mathtt{rmq}/\mathtt{rMq}$ in
$O(1)$ time without accessing $A$.

We further build an auxiliary structure upon a packed sequence $A$ under the
indexing model: after the the data structure is built, $A$ itself need not be
stored verbatim; to answer a query, it suffices to provide an operator that
can retrieve any element in $A$.

######  Lemma 2.11.

Let $A[0..n^{\prime}-1]$ be a packed sequence drawn from alphabet $[\sigma]$,
where $\sigma\leq 2^{\sqrt{\lg n}}$ and $n^{\prime}\leq n$. There is a data
structure using $O(n^{\prime}\lg\lg n)$ extra bits constructed in
$O(n^{\prime}{\lg\sigma}/{\lg n})$ time, which answers
$\mathtt{rmq}/\mathtt{rMq}$ in $O(1)$ time and $O(1)$ accesses to the elements
of $A$. The query procedure uses a universal table of $o(n)$ bits.

##  3 Fast Construction of $\mathtt{rank^{\prime}}$ Query Structures

In this section we focus on how to efficiently construct data structures for
$\mathtt{rank^{\prime}}$ queries over a sequence $A[0..n^{\prime}-1]$ drawn
from alphabet $[\sigma]$, where $n^{\prime}\leq n$ and $\sigma\leq
2^{\sqrt{\lg n}}$. This is needed to solve ball inheritance in a special case
that we need. Lemma 2.7 already solves this problem when $\sigma\leq\lg n$, so
we assume $\lg n<\sigma\leq 2^{\sqrt{\lg n}}$ in the rest of this section.

In our solution, we conceptually divide sequence $A$ into chunks of length
$\sigma$. For simplicity, assume that $n^{\prime}$ is a multiple of $\sigma$.
Let $A_{k}$ denote the $k$th chuck, where $0\leq k\leq n^{\prime}/\sigma-1$.
For each $c\in[0,\sigma-1]$, we define the following data structures:

  * •

A bitvector
$B_{c}=1^{\mathtt{rank}_{c}(A_{0},\sigma)}01^{\mathtt{rank}_{c}(A_{1},\sigma)}0\ldots
1^{\mathtt{rank}_{c}(A_{n^{\prime}/\sigma-1},\sigma)}0$, which encodes the
number of occurrences of symbol $c$ in each chunk in unary. $B_{c}$ is
represented using Lemma 2.8 to support $\mathtt{rank}$ and $\mathtt{select}$
in constant time.

  * •

A sequence $P_{c}[0..n^{\prime}/\sigma-1]$, in which
$P_{c}[i]=\mathtt{rank^{\prime}}(A_{i},c)$ for each
$i\in[0,n^{\prime}/\sigma-1]$, i.e., $P_{c}[i]$ stores the answer to a partial
rank query performed locally within $A_{i}$ at position $c$.

Note that we have one $B_{c}$ for each alphabet symbol $c$, while we have one
$P_{c}$ for each relative position $c$ in the chunks of $A$. The support for
$\mathtt{rank^{\prime}}$ over $A$ follows from:
$\mathtt{rank^{\prime}}(A,j)=\mathtt{select}_{0}(B_{c},t)-(t-1)+P_{\tau}[t],where\
\tau=j\bmod\sigma,t=\lfloor\frac{j}{\sigma}\rfloor,and\ c=A[j]$.

We have the following lemma on supporting queries using these data structures,
with a space analysis.

######  Lemma 3.1.

The data structures in this section occupy
$n^{\prime}\lg\sigma+o(n^{\prime}\lg\sigma)$ extra bits and support
$\mathtt{rank^{\prime}}$ in $O(1)$ time and $O(1)$ accesses to elements of
$A$.

######  Proof 3.2.

See Appendix C.4 for space analysis. A query $\mathtt{rank^{\prime}}(A,j)$ can
be answered as follows:

$\mathtt{rank^{\prime}}(A,j)=select_{0}(B_{c},t)-(t-1)+P_{\tau}[t],where\
\tau=j\bmod\sigma,t=\lfloor\frac{j}{\sigma}\rfloor,and\ c=A[j]$

As the $\mathtt{select}$ query over $B_{c}$ takes constant time, answering
$\mathtt{rank^{\prime}}(A,j)$ requires $O(1)$ time and a single access to $A$.

Next, we consider how to construct the sequences $B_{c}$’s efficiently.

######  Lemma 3.3.

Bitvectors $B_{0},B_{1},\ldots,B_{\sigma-1}$ can be constructed in
$O(n^{\prime}\lg^{2}\sigma/\lg n+\sigma)$ time in total.

######  Proof 3.4.

To construct the sequences $B_{c}$’s, we first construct a sequence
$M[0..n^{\prime}+n^{\prime}/\sigma-1]$ in which each element is encoded in
$\lceil\lg\sigma\rceil+1$ bits. In $M$, $n^{\prime}$ elements are regular
elements, and the rest are boundary elements each of which is an integer whose
binary expression simply consists of $\lceil\lg\sigma\rceil+1$ $0$-bits. $M$
is divided into $n^{\prime}/\sigma$ chunks, and each chunks contains $\sigma$
regular elements followed by a boundary element. The subsequence of the
$\sigma$ regular elements in the $i$-th chunk can be obtained by appending a
$1$-bit to the end of the binary expression of each element in $A_{k}$. $M$
can be computed in $O(n^{\prime}\lg\sigma/\lg n)$ time using a universal table
$U$; See Appendix C.1 for details.

We then construct a tree $T$ over $M$, in which each node $u$ is associated
with a sequence $M(u)$. At the root node $r$ of $T$, we set $M(r)=M$, and we
perform the following recursive procedure at any node $u$ at level $l$ of $T$
where $l\in[0,\lceil\lg\sigma\rceil-1]$: We create the left child, $u_{0}$,
and the right child, $u_{1}$, of $u$, and perform a linear scan of $M(u)$.
During the scan, for each $i\in[0,|M(u)-1|]$, if $M(u)[i]$ is a boundary
element, it is appended to both $M(u_{0})$ and $M(u_{1})$. If $M(u)[i]$ is not
a boundary element and its $l$th most significant bit is $0$, $M(u)[i]$ is
appended to $M(u_{0})$. If its most significant bit is $1$, it is appended to
$M(u_{1})$. After generating the sequences $M(u_{0})$ and $M(u_{1})$, we
discard the sequence $M(u)$. We finish recursion after we create
$\lceil\lg\sigma\rceil$ levels, i.e., we only examine the first
$\lceil\lg\sigma\rceil$ bits of each element of $M$ to determine the tree
structure. Thus, this tree has $\sigma$ leaves, and the sequences associated
with the leaves from left to right are named $M_{0}$, $M_{1}$, …,
$M_{\sigma-1}$. They form a partition of $M$.

To speed up this process, we use a universal table $U^{\prime}$ of $o(n)$ bits
described in Appendix C.2, which allows us to process $M(u)$ in
$O(|M(u)|\lg\sigma/\lg n+1)$ time. Note that we assign $n^{\prime}$ regular
and $2^{l}\times\frac{n^{\prime}}{\sigma}$ boundary elements to the nodes at
tree level $l$. Thus the total time required to construct $T$ is
$O(\sum_{l=0}^{\lceil\lg\sigma\rceil-1}((n^{\prime}+2^{l}\times\frac{n^{\prime}}{\sigma})\lg\sigma/\lg
n)+\sigma)=O(n^{\prime}\lg^{2}\sigma/\lg n+\sigma)$.

To compute $B_{c}$ for any $0\leq c\leq\sigma-1$, a crucial observation is
that the $i$-th bit in $B_{c}$ is the same as the least significant bit of the
$i$-th element of $M_{c}$. Thus it takes $O(|B_{c}|(\lg\sigma+1)/\lg n+1)$
time to compute the content of $B_{c}$ using bit packing (see Lemma A.1). The
time to represent $B_{c}$ using Lemma 2.8 is less. Thus the time used to build
$B_{0}$, $B_{1}$, …, $B_{\sigma-1}$ from $M_{0},M_{1},\ldots,M_{\sigma-1}$ is
$O(n^{\prime}\lg\sigma/\lg n+\sigma)$, dominated by the time of building $T$.

We show how to efficiently construct $P_{0},P_{1},\ldots,P_{\sigma-1}$ in
Appendix C.3. See Appendix C.4 for the space analysis of all data structure
designed. Our work in this section combined with Lemmas 2.7 yields the
following result.

######  Lemma 3.5.

Let $A[0..n^{\prime}-1]$ be a packed sequence drawn from alphabet $[\sigma]$,
where $n^{\prime}\leq n$ and $\sigma=O(2^{O(\sqrt{\lg n})})$. A data structure
using $n^{\prime}\lceil\lg\sigma\rceil+o(n^{\prime}\lg\sigma)$ extra bits can
be constructed in $O(n^{\prime}{\lg^{2}\sigma}/{\lg n}+\sigma)$ time to
support $\mathtt{rank^{\prime}}$ in $O(1)$ time and $O(1)$ accesses to
elements of $A$.

##  4 Fast Construction of Data Structures for Ball Inheritance

We now solve, with fast preprocessing, ball inheritance for the special cases
needed later to match the time and space bounds in parts (b) and (c) of Lemma
2.6. The omitted proofs are in Appendix D. One strategy is to construct the
solution of Chan et al. [11] by replacing some of their components with those
we designed with faster preprocessing. This yields:

######  Lemma 4.1.

Let $X[0,n-1]$ be a sequence drawn from alphabet $[\sigma]$ denoting the point
set $N=\\{(X[i],i)|0\leq i\leq n-1\\}$, where $2^{\sqrt{\lg n}}\leq\sigma\leq
n$. A $2^{\sqrt{\lg n}}$-ary wavelet tree over $X$ occupying
$O(n\lg\sigma\cdot f(\sigma)+n\lg n)$ bits can be constructed in
$O(n\lg\sigma/\sqrt{\lg n})$ time to support $\mathtt{point}$ in
$O(g(\sigma))$ time and $\mathtt{noderange}$ in $O(\lg\lg n+g(\sigma))$ time,
where (a) $f(\sigma)=O(\lg(\lg\sigma/\sqrt{\lg n}))$ and
$g(\sigma)=O(\lg(\lg\sigma/\sqrt{\lg n}))$; or (b)
$f(\sigma)=O(\lg^{\epsilon}\sigma)$ and $g(\sigma)=O(1)$ for any constant
$\epsilon>0$. The $\mathtt{noderange}$ query requires a universal table of
$o(n)$ bits.

######  Lemma 4.2.

Let $X[0..n^{\prime}-1]$ be a packed sequence drawn from alphabet $[\sigma]$
and $Y[0..n^{\prime}-1]$ be a packed sequence in which $Y[i]=i$ for each
$i\in[0..n^{\prime}-1]$, where $\sigma=O(2^{O(\sqrt{\lg n})})$ and
$n^{\prime}=O(\sigma^{O(1)})$. Given $X$ and $Y$ as input, a $d$-ary wavelet
tree over $X$ using $O(n^{\prime}\lg\sigma\lg(\lg\sigma/\lg d)+\sigma w)$ bits
of space can be constructed in $O(n^{\prime}{\lg^{2}\sigma}/{\lg
n}+\sigma\log_{d}\sigma)$ time to support $\mathtt{point}$ in
$O(\lg(\lg\sigma/\lg d))$ time and $\mathtt{noderange}$ in $O(\lg\lg\sigma)$
time, where $d$ is a power of $2$ upper bounded by $min(\sigma,2^{\sqrt{\lg
n}})$.

This strategy however cannot achieve, with the preprocessing time as in Lemma
4.2, part (c) of Lemma 2.6 when the coordinates of points can be encoded in
$O(\sqrt{\lg n})$ bits. For this special case, we twist the approach of Chan
et al.: they only store point coordinates explicitly at the leaf level of the
wavelet tree, while we take advantage of the smaller grid size to store
coordinates at more levels. This allows us to build $\mathtt{rank^{\prime}}$
structures at fewer levels of the tree, decreasing the preprocessing time. The
details are as follows.

Recall that, when used to represent the given point set $N$, each node, $u$,
of the $d$-ary wavelet tree $T$ is conceptually associated with an ordered
list, $N(u)$, of points whose $x$-coordinates are within the range represented
by $u$, and these points are ordered by $y$-coordinate. Assume for simplicity
that $\sigma$ is a power of $d$, and that both $1/\epsilon$ and
$\tau=\log_{d}^{\epsilon}\sigma$ are integers. We assign a color to each level
of $T$: Level $0$ is assigned color $0$, while any other Level $l$ is assigned
color $\max\\{c\ |\ l\text{ is divided by }\tau^{c}\text{ and }0\leq c\leq
1/\epsilon-1\\}$. For each node $u$ of $T$ at a level assigned with color
$1/\epsilon-1$, we store the coordinates of the points in $N(u)$ explicitly.
For any other node $v$ (let $l$ be the level $l$ of $v$ and $c$ the color
assigned to level $l$), we do not store $N(v)$. Instead, for each
$i\in[0,|N(v)|]$, we store a skipping pointer $\mathit{S\\!p}(v)[i]$, which
stores, at the closest level $l^{\prime}$ satisfying $l^{\prime}>l$ and
$l^{\prime}$ is a multiple of $\tau^{c+1}$, the descendant of $v$ at level
$l^{\prime}$ containing point $N(v)[i]$ in its ordered list of points. This
descendant is encoded by its rank among all the descendants of $v$ at level
$l^{\prime}$ in left-to-right order. We use Lemma 3.5 to support $O(1)$-time
$\mathtt{rank^{\prime}}$ over $\mathit{S\\!p}(v)$. Then, since both $N(u)$ and
$N(\mathit{S\\!p}(u)[i])$ order points by $y$-coordinate, a
$\mathtt{rank^{\prime}}(\mathit{S\\!p}(u),i)$ query gives the position of the
point $N(u)[i]$ in $N(\mathit{S\\!p}(u)[i])$. Thus, to compute
$\mathtt{point}(v,i)$, we follow skip pointers starting from $v$ by performing
$\mathtt{rank^{\prime}}$, until we reach a level with color $1/\epsilon-1$,
where we retrieve coordinates. With this we have:

######  Lemma 4.3.

Let $X[0..n^{\prime}-1]$ be a packed sequence drawn from alphabet $[\sigma]$
and $Y[0..n^{\prime}-1]$ be a packed sequence in which $Y[i]=i$ for each
$i\in[0..n^{\prime}-1]$, where $\sigma=O(2^{O(\sqrt{\lg n})})$ and
$n^{\prime}=O(\sigma^{O(1)})$. Given $X$ and $Y$ as input, a $d$-ary wavelet
tree over $X$ using $O(n^{\prime}\lg\sigma\log_{d}^{\epsilon}\sigma+\sigma w)$
bits for any positive constant $\epsilon$ can be constructed in
$O(n^{\prime}{\lg^{2}\sigma}/{\lg n}+\sigma\log_{d}\sigma)$ time to support
$\mathtt{point}$ in $O(1)$ time and $\mathtt{noderange}$ in $O(\lg\lg\sigma)$
time, where $d$ is a power of $2$ upper bounded by $min(\sigma,2^{\sqrt{\lg
n}})$. The $\mathtt{noderange}$ query requires a universal table of $o(n)$
bits.

##  5 Optimal Orthogonal Range Reporting with Fast Preprocessing

We now design structures that support orthogonal range reporting in optimal
time and can be constructed fast. We follow the solution overview given in
Section 1: We first reduce the problem in the general case to the special case
in which the points are from a $2^{\sqrt{\lg n}}\times n^{\prime}$ (narrow)
grid, In this reduction, we need only support ball-inheritance over a wavelet
tree with high fanout which is solved by part (b) of Lemma 4.1. We then
further reduce it to the range reporting problem over a (small) grid of size
at most $2^{\sqrt{\lg n}}\times 2^{2\sqrt{\lg n}}$, to which we apply Lemma
4.3 for ball inheritance.

The following two lemmas present our solution for small and then narrow girds:

######  Lemma 5.1.

Let $N$ be a set of $\delta$ points with distinct $y$-coordinates in a
$2^{\sqrt{\lg n}}\times\delta$ grid where $\delta\leq 2^{2\sqrt{\lg n}}$.
Given packed sequences $X$ and $Y$ respectively encoding the $x$\- and
$y$-coordinates of these points where $Y[i]=i$ for any $i\in[0,\delta-1]$, a
data structure of $O(\delta\lg^{1/2+\epsilon}n+w\cdot 2^{\sqrt{\lg n}})$ bits
can be constructed in $O(\delta+\sqrt{\lg n}\cdot 2^{\sqrt{\lg n}})$ time to
support orthogonal range reporting over $N$ in $O(\lg\lg n+\mathtt{occ})$ time
with the help of an $o(n)$-bit universal table, where $\epsilon$ is an
arbitrary positive constant and $\mathtt{occ}$ is the number of reported
points.

######  Proof 5.2.

We build a binary wavelet tree $T$ over $X$ augmented with support for ball
inheritance. By Lemma 4.3, $T$ occupies $O(\delta\lg^{1/2+\epsilon}n+w\cdot
2^{\sqrt{\lg n}})$ bits and can be built in $O(\delta+\sqrt{\lg n}\cdot
2^{\sqrt{\lg n}})$ time. It also supports $\mathtt{point}$ in $O(1)$ time and
$\mathtt{noderange}$ in $O(\lg\lg n)$ time. For any internal node $v$ of $T$,
its value array $A(v)$ is built at some point when augmenting $T$ to solve
ball inheritance, though $A(v)$ may be discarded eventually. When $A(v)$ was
available, we build a data structure $M(v)$ to support range minimum and
maximum queries over $A(v)$ using Lemma 2.11. As $T$ has $\lceil\sqrt{\lg
n}\rceil$ non-leaf levels and the total length of the value arrays of the
nodes at each tree level is $\delta$, over all internal nodes, these
structures use $O(\delta\sqrt{\lg n}\lg\lg n)$ bits in total and the overall
construction time is $\sum_{v}O({|A(v)|}/{\sqrt{\lg
n}}+1)=O(\delta+2^{\sqrt{\lg n}})$. These costs are subsumed in the storage
and construction costs of $T$. Recall that $A(v)$ stores the $x$-coordinates
of the set, $N(v)$, of points from $N$ whose $x$-coordinates are within the
range represented by $v$, and the entries of $A(v)$ are ordered by the
corresponding $y$-coordinates of these points. Thus any entry of $A(v)$ can be
retrieved by $\mathtt{point}$ in constant time. Therefore, even after $A(v)$
is discarded, $M(v)$ can still support $\mathtt{rmq}$/$\mathtt{rMq}$ over
$A(v)$ in $O(1)$ time.

Given a query range $Q=[a,b]\times[c,d]$, we first locate the lowest common
ancestor $u$ of $l_{a}$ and $l_{b}$ in constant time, where $l_{a}$ and
$l_{b}$ denote the $a$-th and $b$-th leftmost leaves of $T$, respectively. Let
$u_{l}$ and $u_{r}$ denote the left and right children of $u$, respectively,
$[c_{l},d_{l}]=\mathtt{noderange}(c,d,u_{l})$ and
$[c_{r},d_{r}]=\mathtt{noderange}(c,d,u_{r})$. Then $Q\cap
N=(([a,+\infty)\times[c_{l},d_{l}])\cap
N(u_{l}))\cup(([0,b]\times[c_{r},d_{r}])\cap N(u_{r}))$. In this way, we
reduce a $2$-d $4$-sided range reporting in $N$ to $2$-d $3$-sided range
reporting in $N(u_{l})$ and $N(u_{r})$. Each $3$-sided range reporting can be
solved in optimal time by performing $\mathtt{rMq}$ and $\mathtt{rmq}$ over
$A(u_{l})$ and $A(u_{r})$ recursively as done by Chan et al. [11]; for
completeness, we provide the details in Appendix E.1. Thus the overall query
time is $O(\lg\lg n+\mathtt{occ})$.

######  Lemma 5.3.

Let $N$ be a set of $n^{\prime}$ points with distinct $y$-coordinates in a
$2^{\sqrt{\lg n}}\times n^{\prime}$ grid where $n^{\prime}\leq n$. Given
packed sequences $X$ and $Y$ respectively encoding the $x$\- and
$y$-coordinates of these points where $y[i]=i$ for any $i\in[0,\delta-1]$, a
data structure occupying $O(n^{\prime}\lg^{1/2+\epsilon}n+w(2^{\sqrt{\lg
n}}+n^{\prime}/2^{\sqrt{\lg n}}))$ bits can be constructed in
$O(n^{\prime}+\sqrt{\lg n}\cdot 2^{\sqrt{\lg n}})$ time to support orthogonal
range reporting over $N$ in $O(\lg\lg n+\mathtt{occ})$ time with the help of
an $o(n)$-bit universal table, where $\epsilon$ is an arbitrary positive
constant and $\mathtt{occ}$ is the number of reported points.

######  Proof 5.4.

Let $b=2^{2\sqrt{\lg n}}$. We need only consider the case in which
$n^{\prime}>b$ as Lemma 5.1 applies otherwise. Assume for simplicity that
$n^{\prime}$ is divisible by $b$. We divide $N$ into $n^{\prime}/b$ subsets,
and for each $i\in[0,n^{\prime}/b-1]$, the $i$th subset, $N_{i}$, contains
points in $N$ whose $y$-coordinates are in $[ib,(i+1)b-1]$. Let $p$ be a point
in $N_{i}$. We call its coordinates $(p.x,p.y)$ global coordinates, while
$(p.x^{\prime},p.y^{\prime})=(p.x,p.y\bmod b)$ its local coordinates in
$N_{i}$; the conversion between global and local coordinates can be done in
constant time. With the local coordinates, We can apply Lemma 5.1 to construct
an orthogonal range search structure over each $N_{i}$. We also define a point
set $\hat{N}$ in a $2^{\sqrt{\lg n}}\times n^{\prime}/b$ grid. For each set
$N_{i}$ where $i\in[0,n^{\prime}/b-1]$ and each $j\in[0,2^{\sqrt{\lg n}}-1]$,
we store a point $(j,i)$ in $\hat{N}$ iff there exists at least one point in
$N_{i}$ whose $x$-coordinate is $j$. Thus the number of points in $\hat{N}$ is
at most $n^{\prime}/b\times 2^{\sqrt{\lg n}}=n^{\prime}/2^{\sqrt{\lg n}}$.
$|\hat{N}|$ is small enough for us to build the optimal range reporting
structure of Chan et al. [11, Section 2],[7, Lemma 5]. In addition, for each
$i\in[0,n^{\prime}/b-1]$ and $j\in[0,2^{\sqrt{\lg n}}-1]$, we store a list
$P_{i,j}$ storing the local $y$-coordinates of the points in $N_{i}$ whose
$x$-coordinates are equal to $j$. See Appendix E.1 for the analysis of the
space usage and the construction time.

Given a query range $Q=[x_{1},x_{2}]\times[y_{1},y_{2}]$, we first check if
$\lfloor y_{1}/b\rfloor$ is equal to $\lfloor y_{2}/b\rfloor$. If it is, then
the points in the answer to the query reside in the same subset $N_{\lfloor
y_{1}/b\rfloor}$, and they can be reported in $O(\lg\lg n+\mathtt{occ})$ time
by Lemma 5.1. Otherwise, we decompose $Q$ into three subranges
$Q_{1}=[x_{1},x_{2}]\times[y_{1},b(\lfloor y_{1}/b\rfloor+1)-1]$,
$Q_{2}=[x_{1},x_{2}]\times[b(\lfloor y_{1}/b\rfloor+1),b\lfloor
y_{2}/b\rfloor-1]$ and $Q_{3}=[x_{1},x_{2}]\times[b\lfloor
y_{2}/b\rfloor,y_{2}]$. The points in $N\cap Q_{1}$ and $N\cap Q_{3}$ are in
$N_{\lfloor y_{1}/b\rfloor}$ and $N_{\lfloor y_{2}/b\rfloor}$, respectively,
and by Lemma 5.1, they can be reported in optimal time. The points in $N\cap
Q_{2}$ are in $N_{\lfloor y_{1}/b\rfloor+1},N_{\lfloor
y_{1}/b\rfloor+2},\ldots,N_{\lfloor y_{2}/b\rfloor-1}$. To retrieve them, we
first perform an orthogonal range query in $\hat{N}$ with query range
$\hat{Q}=[x_{1},x_{2}]\times[\lfloor y_{1}/b\rfloor+1,\lfloor
y_{2}/b\rfloor-1]$. For each point $(x,y)\in\hat{N}\cap\hat{Q}$, we observe
that its existence means that is at least one point in $N_{y}\cap Q_{2}$ whose
$x$-coordinates are equal to $x$; we retrieve the local $y$-coordinates of
these points from $P_{y,x}$. The overall query time is thus $O(\lg\lg
n+\mathtt{occ})$.

We now describe a solution in which the grid size is $\sigma\times n$ with
$2^{\sqrt{\lg n}}\leq\sigma\leq n$. This is more general than our final
result, but it will be needed for an application later.

######  Lemma 5.5.

Given a sequence $X[0,n-1]$ drawn from alphabet $[\sigma]$ denoting the point
set $N=\\{(X[i],i)|0\leq i\leq n-1\\}$, a data structure of
$O(n\lg^{1+\epsilon}\sigma+n\lg n)$ bits for any constant $\epsilon>0$ can be
constructed in $O(n{\lg\sigma}/{\sqrt{\lg n}})$ time to support orthogonal
range reporting over $N$ in $O(\lg\lg n+\mathtt{occ})$ time, where
$2^{\sqrt{\lg n}}\leq\sigma\leq n$ and $\mathtt{occ}$ is the number of
reported points.

######  Proof 5.6.

We build a $2^{\sqrt{\lg n}}$-ary wavelet tree $T$ upon $X[0,n-1]$ with
support for ball inheritance using part (b) of Lemma 4.1. As in the proof of
Lemma 5.1, for each internal node $v\in T$, we build a data structure $M(v)$
to support $\mathtt{rMq}/\mathtt{rmq}$ over its value array $A(v)$ in constant
time using Lemma 2.10, even though $A(v)$ is not be explicitly stored.
Conceptually, let $N(v)$ denote an ordered list of points from $N$ whose
$x$-coordinates are within the range represented by $v$, and these points are
ordered by $y$-coordinate. Recall that $v$ is associated with sequence $S(v)$
drawn from alphabet $[2^{\sqrt{\lg n}}]$, where $S(v)[i]$ encodes the rank of
the child of $v$ that contains $N(v)[i]$ in its ordered list. Let $\hat{S}(v)$
denote the point set $\\{(S(v)[i],i)|0\leq i\leq|S(v)|-1\\}$, and we use Lemma
5.3 to build a structure supporting orthogonal range reporting over
$\hat{S}(v)$. See Appendix E.3 for the analysis of the space usage and the
construction time.

Given a query range $Q=[a,b]\times[c,d]$, we first locate the lowest common
ancestor $u$ of $l_{a}$ and $l_{b}$ in constant time, where $l_{a}$ and
$l_{b}$ denote the $a$-th and $b$-th leftmost leaves of $T$, respectively. Let
$u_{i}$ denote the $i$-th child of $u$, for any $i\in[0,2^{\sqrt{\lg n}}-1]$.
We first locate two children, $u_{a^{\prime}}$ and $u_{b^{\prime}}$, of $u$
that are ancestors of $l_{a}$ and $l_{b}$, respectively. They can be found in
constant time by simple arithmetic as each child of $u$ represents a range of
equal size. Then the answer, $Q\cap N$, to the query can be partitioned into
three point sets $A_{1}=Q\cap N(v_{a^{\prime}})$,
$A_{2}=Q\cap(N(v_{a^{\prime}+1})\cup N(v_{a^{\prime}+2})\cup\ldots
N(v_{b^{\prime}-1}))$ and $A_{3}=Q\cap N(v_{b^{\prime}})$. As in the proof of
Lemma 5.1, $A_{1}$ and $A_{3}$ can be computed in in $O(\lg\lg
n+|A_{1}|+|A_{3}|)$ time using $\mathtt{noderange}$ and
$\mathtt{rmq}$/$\mathtt{rMq}$. To compute $A_{2}$, observe that by performing
range reporting over $\hat{S}$ to compute
$S\cap([a^{\prime}+1,b^{\prime}-1]\times[c_{v},d_{v}])$, where
$[c_{v},d_{v}]=\mathtt{noderange}(c,d,v)$, we can find the set of points in
$\hat{S}(v)$ corresponding to the points in $A_{2}$. For each point returned,
we use $\mathtt{point}$ to find its original coordinates in $N$ and return it
as part of $A_{2}$. This process uses $O(\lg\lg n+|A_{2}|)$ time. Hence we can
compute $Q\cap N$ as $A_{1}\cup A_{2}\cup A_{3}$ in $O(\lg\lg n+\mathtt{occ})$
time.

Our result on points over an $n\times n$ gird immediately follows.

######  Theorem 5.7.

Given $n$ points in rank space, a data structure of $O(n\lg^{\epsilon}n)$
words for any constant $\epsilon>0$ can be constructed in $O(n\sqrt{\lg n})$
time to support orthogonal range reporting in $O(\lg\lg n+\mathtt{occ})$ time,
where $\mathtt{occ}$ is the number of reported points.

##  6 Optimal Orthogonal Range Successor with Fast Preprocessing

In this section, we assume that a range successor query asks for the lowest
point in the query rectangle. The following theorem presents our result on
fast construction of structures for optimal range successor; we provide a
proof sketch, and the full proof is in Appendix F:

######  Theorem 6.1.

Given $n$ points in rank space, a data structure of $O(n\lg\lg n)$ words can
be constructed in $O(n\sqrt{\lg n})$ time to support orthogonal range
successor in $O(\lg\lg n)$ time.

######  Proof 6.2 (Proof (sketch)).

Our approach is similar to that in Section 5, but more levels of reductions
are required. Let the sequence $X[0,n-1]$ denote the point set
$N=\\{(X[i],i)|0\leq i\leq n-1\\}$. We build a $2^{\sqrt{\lg n}}$-ary wavelet
tree $T$ upon $X[0,n-1]$ with support for ball inheritance using part (a) of
Lemma 4.1. As shown in the proof of Lemma 5.5, a query can be answered by
locating the lowest common ancestor, $u$, of the two leaves corresponding to
the end points of the query $x$-range, and then performing two $3$-sided
queries over the point sets represented by two children of $u$ and one
$4$-sided query over $S(u)$. For the $3$-sided queries, Zhou [32] already
designed an indexing structure, which, with our $O(\lg\lg n)$-time support for
$\mathtt{point}$ and $\mathtt{noderange}$, can answer a $3$-sided query in
$O(\lg\lg n)$ time. The construction time is linear, but it is fine since $T$
has only $O(\sqrt{\lg n})$ levels. The $4$-side query over $S(u)$ is a range
successor query over $n^{\prime}$ points in a $2^{\sqrt{\lg n}}\times
n^{\prime}$ (medium narrow) grid for any $n^{\prime}\leq n$.

For such a medium narrow grid, we use the sampling strategy in Lemma 5.3 to
reduce the problem to range successor over a set of $n^{\prime}$ points in a
$2^{\sqrt{\lg n}}\times n^{\prime}$ grid where $n^{\prime}\leq 2\times
2^{2{\sqrt{\lg n}}}-1$. The sampling is adjusted, as we need select at most
$2^{\sqrt{\lg n}}$ sampled points from each subset. The grid size of
$2^{\sqrt{\lg n}}\times n^{\prime}$ with $n^{\prime}\leq 2\times
2^{2{\sqrt{\lg n}}}-1$ is the same as that in Lemma 5.1, so one may be tempted
to apply the same strategy of building a binary wavelet tree to reduce it to
the problem of building index structures for $3$-sided queries. However, we
found that, to construct the structure of Zhou [32] over $n^{\prime}$ points
whose coordinates are encoded in $O(\sqrt{\lg n})$ bits, $O(n^{\prime}\lg\lg
n/\sqrt{\lg n})$ time is required, which is a factor of $\lg\lg n$ more than
the preprocessing time of the $\mathtt{rmq}$ structure needed in the proof of
Lemma 5.1. This factor comes from rank reduction in [32], which requires us to
sort packed sequences. To overcome this additional cost, we build a
$\lg^{1/4}n$-ary wavelet tree over the $x$-coordinates, whose number of levels
is a factor of $O(\lg\lg n)$ less than that of a binary wavelet tree. As
discussed for the general case, this strategy reduces the current problem to
orthogonal range successor over $n^{\prime}$ points in an $\lg^{1/4}n\times
n^{\prime}$ (small narrow) grid with $n^{\prime}\leq n$.

For a small narrow grid, there are two cases. If $n^{\prime}>\lg n$, we build
a binary wavelet tree of height $O(\lg\lg n)$. In the query algorithm, after
finding the lowest common ancestor of the two leaves corresponding to the end
points of the query $x$-range, we do not perform 3-sided queries. Instead, we
traverse the two paths leading to these two leaves. This requires us to
traverse down $O(\lg\lg n)$ levels, and at each level, we perform certain
$\mathtt{rank}$/$\mathtt{select}$ operations in constant time, with the right
auxiliary structures at each node. No extra support for ball inheritance is
needed as we can simply go down the tree level by level to map information.
Finally, if $n^{\prime}<\lg n$, we use sampling to reduce it to even smaller
grids of size at most $\lg^{1/4}n\times\lg^{3/4}n$, over which a query can be
answered using a table lookup.

##  7 Applications

We now apply our range search structures to the text indexing problem, in
which we preprocess a text string $T\in[\sigma]^{n}$, where $\sigma\leq n$.
Given a pattern string $P[0..p-1]$, a counting query computes the number of
occurrences of $P$ in $T$ and a listing query reports these occurrences.

##### Text indexing and searching in sublinear time.

When both $T$ and $P$ are given in packed form, a text index of Munro et al.
[26] occupies $O(n\lg\sigma)$ bits, can be built in $O(n\lg\sigma/\sqrt{\lg
n})$ time and supports counting queries in $O(p/\log_{\sigma}n+\lg
n\log_{\sigma}n)$ time (there are other tradeoffs, but this is their main
result). Thus for small alphabet size which is common in practice, they
achieve both $o(n)$ construction time and $o(p)$ query time, while previous
results achieve at most one of these bounds. To support listing queries,
however, they need to increase space cost to $O(n\lg\sigma\lg^{\epsilon}n)$
bits and construction time to $O(n\lg\sigma\lg^{\epsilon}n)$, and then a
listing query can be answered in $O({p}/{\log_{\sigma}n}+\log_{\sigma}n\lg\lg
n+\mathtt{occ})$. The increase in storage and construction costs stems from
one component they used which is an orthogonal range reporting structure over
$t=O(n/r)$ points in a $\sigma^{O(r)}\times t$ grid, for $r=c\log_{\sigma}n$
for any constant $c<1/4$. We can apply Lemma 5.5 over this point set to
decrease the construction time of their index for listing queries to match
that for counting queries:

Their text index [26, Theorem 2] occupies $O((n/r)\lg n)$ bits, can be built
in $O(n((\lg\lg n)^{2}/r+\lg\sigma/\sqrt{\lg n}))$ time and supports counting
queries in $O(p/\log_{\sigma}n+r^{2}\lg\sigma+r\lg\lg n)$ time, for any
$0<r<(1/4)\log_{\sigma}n$. Thus for small alphabet size which is common in
practice, they achieve both $o(n)$ construction time and $o(p)$ query time,
while previous results achieve at most one of these bounds but not both. To
support listing queries, however, they need to increase space cost to
$O((n/r)\lg n+n\lg\sigma\lg^{\epsilon}n)$ bits and construction time to
$O(n((\lg\lg n)^{2}/r+(r\lg^{2}\sigma)/\lg^{1-\epsilon}n))$ for any constant
$0<\epsilon<1$, and then a listing query can be answered in
$O({p}/{\log_{\sigma}n}+r\lg\lg n+\mathtt{occ})$ time, where $\mathtt{occ}$ is
the number of occurrences of $P$ in $T$. The source of the increase in storage
and construction costs stems from one component they used which is an
orthogonal range reporting structure over $t=O(n/r)$ points in a
$\sigma^{O(r)}\times t$ grid. This structure occupies
$O(n\lg\sigma\lg^{\epsilon}n)$ bits, can be constructed in
$O(n(r\lg^{2}\sigma)/\lg^{1-\epsilon}n)$ time and supports orthogonal range
reporting queries in time $O(\lg\lg n+\mathtt{occ})$. While the query time and
space cost of this data structure matches the current best result, we can
improve the construction time when $r=c\log_{\sigma}n$ for any constant
$c<1/4$. This is because the $x$-coordinate of each point can be encoded with
$\Theta(r\lg\sigma)=\Theta(\lg n)=\Omega(\sqrt{\lg n})$ bits. Thus, Lemma 5.5
applies for sufficiently large $n$, and this means we can construct an
orthogonal range reporting structure over these points in $O((n/r)\times
r\lg\sigma/{\sqrt{\lg n}})=O(n\lg\sigma/\sqrt{\lg n})$ time, while the space
cost and query time remain the same. As a result, we can improve their index
for listing queries by decreasing construction time to match that for counting
queries:

######  Theorem 7.1.

Given a packed text string $T$ of length $n$ over an alphabet of size
$\sigma$, an index of $O(n\lg\sigma\lg^{\epsilon}n)$ bits can be built in
$O(n\lg\sigma/\sqrt{\lg n})$ time for any positive constant $\epsilon$. Given
a packed pattern string $P$ of length $p$, this index supports listing queries
in $O({p}/{\log_{\sigma}n}+\log_{\sigma}n\lg\lg n+\mathtt{occ})$ time where
$\mathtt{occ}$ is the number of occurrences of $P$ in $T$.

##### Position-restricted substring search.

In a position-restricted substring search [24], we are given both a pattern
$P$ and two indices $0\leq l\leq r\leq n-1$, and we report all occurrences of
$P$ in $T[l..r]$. Makinen and Navarro [24] solves this problem using an index
for the original text indexing problem and a two-dimensional orthogonal range
reporting structure. Different text indexes and range reporting structures
yield different tradeoffs. The tradeoff with the fastest query time supports
position-restricted substring search in $O(p+\lg\lg n+\mathtt{occ})$ time,
where $\mathtt{occ}$ is the output size, and it uses $O(n\lg^{1+\epsilon}n)$
bits and can be constructed in $O(n\lg n)$ time. Again, the construction time
of the range reporting structure is the bottleneck, which can be improved by
Theorem 5.7. We can also use a new text index by Bille et al. [8] to achieve
speedup when $P$ is given as a packed sequence. We have:

######  Theorem 7.2.

Given a text $T$ of length $n$ over an alphabet of size $\sigma$, an index of
$O(n\lg^{1+\epsilon}n)$ bits can be built in $O(n\sqrt{\lg n})$ time for any
constant $0<\epsilon<1/2$. Given a packed pattern string $P$ of length $p$,
this index supports position-restricted substring search in
$O({p}/{\log_{\sigma}n}+\lg p+\lg\lg\sigma+\mathtt{occ})$ time, where
$\mathtt{occ}$ in the size of the output.

## References

  * [1] Susanne Albers and Torben Hagerup.  Improved parallel integer sorting without concurrent writing.  Information and Computation, 136(1):25–51, 1997.  doi:10.1006/inco.1997.2632.
  * [2] Stephen Alstrup, Gerth Stølting Brodal, and Theis Rauhe.  New data structures for orthogonal range searching.  In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA, pages 198–207. IEEE Computer Society, 2000.
  * [3] Maxim Babenko, Paweł Gawrychowski, Tomasz Kociumaka, and Tatiana Starikovskaya.  Wavelet trees meet suffix trees.  In 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 572–591. Society for Industrial and Applied Mathematics, 2015.
  * [4] Djamal Belazzougui, Fabio Cunial, Juha Kärkkäinen, and Veli Mäkinen.  Linear-time string indexing and analysis in small space.  ACM Transactions on Algorithms (TALG), 16(2):1–54, 2020.
  * [5] Djamal Belazzougui and Simon J Puglisi.  Range predecessor and lempel-ziv parsing.  In 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2053–2071. Society for Industrial and Applied Mathematics, 2016.
  * [6] Michael A Bender and Martın Farach-Colton.  The level ancestor problem simplified.  Theoretical Computer Science, 321(1):5–12, 2004.
  * [7] Philip Bille and Inge Li Gørtz.  Substring range reporting.  Algorithmica, 69(2):384–396, 2014.  doi:10.1007/s00453-012-9733-4.
  * [8] Philip Bille, Inge Li Gørtz, and Frederik Rye Skjoldjensen.  Deterministic indexing for packed strings.  In 28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017, July 4-6, 2017, Warsaw, Poland, pages 6:1–6:11, 2017.  doi:10.4230/LIPIcs.CPM.2017.6.
  * [9] Prosenjit Bose, Meng He, Anil Maheshwari, and Pat Morin.  Succinct orthogonal range search structures on a grid with applications to text indexing.  In 11th International Symposium on Algorithms and Data Structures, volume 5664 of Lecture Notes in Computer Science, pages 98–109. Springer, 2009.
  * [10] Timothy M Chan, Meng He, J Ian Munro, and Gelin Zhou.  Succinct indices for path minimum, with applications.  Algorithmica, 78(2):453–491, 2017.
  * [11] Timothy M Chan, Kasper Green Larsen, and Mihai Pătraşcu.  Orthogonal range searching on the ram, revisited.  In 27th Symposium on Computational Geometry, pages 1–10. ACM, 2011\.
  * [12] Timothy M. Chan and Mihai Pǎtraşcu.  Counting inversions, offline orthogonal range counting, and related problems.  In 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 161–173, 2010.  doi:10.1137/1.9781611973075.15.
  * [13] Bernard Chazelle.  A functional approach to data structures and its use in multidimensional searching.  SIAM Journal on Computing, 17(3):427–462, 1988.
  * [14] Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, M. Sohel Rahman, German Tischler, and Tomasz Walen.  Improved algorithms for the range next value problem and applications.  Theoretical Computer Science, 434:23–34, 2012.
  * [15] Maxime Crochemore, Marcin Kubica, Tomasz Walen, Costas S. Iliopoulos, and M. Sohel Rahman.  Finding patterns in given intervals.  Fundamenta Informaticae, 101(3):173–186, 2010.  doi:10.3233/FI-2010-283.
  * [16] Johannes Fischer and Volker Heun.  Space-efficient preprocessing schemes for range minimum queries on static arrays.  SIAM Journal on Computing, 40(2):465–492, 2011.
  * [17] Michael L. Fredman and Dan E. Willard.  Trans-dichotomous algorithms for minimum spanning trees and shortest paths.  Journal of Computer and System Sciences, 48(3):533–551, 1994.  doi:10.1016/S0022-0000(05)80064-9.
  * [18] Roberto Grossi, Alessio Orlandi, Rajeev Raman, and S. Srinivasa Rao.  More haste, less waste: Lowering the redundancy in fully indexable dictionaries.  In 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, February 26-28, 2009, Freiburg, Germany, Proceedings, pages 517–528, 2009.  doi:10.4230/LIPIcs.STACS.2009.1847.
  * [19] Joseph JáJá, Christian Worm Mortensen, and Qingmin Shi.  Space-efficient and fast algorithms for multidimensional dominance reporting and counting.  In 15th International Symposium on Algorithms and Computation, volume 3341 of Lecture Notes in Computer Science, pages 558–568. Springer, 2004.
  * [20] Jesper Jansson, Zhaoxian Li, and Wing-Kin Sung.  On finding the adams consensus tree.  Information and Computation, 256:334–347, 2017.  doi:10.1016/j.ic.2017.08.002.
  * [21] Orgad Keller, Tsvi Kopelowitz, and Moshe Lewenstein.  Range non-overlapping indexing and successive list indexing.  In 10th Workshop on Algorithms and Data Structures 2007, Halifax, Canada, August 15-17, 2007, Proceedings, volume 4619 of Lecture Notes in Computer Science, pages 625–636. Springer, 2007.
  * [22] Hans-Peter Lenhof and Michiel H. M. Smid.  Using persistent data structures for adding range restrictions to searching problems.  Informatique Theorique et Applications, 28(1):25–49, 1994.  doi:10.1051/ita/1994280100251.
  * [23] Moshe Lewenstein.  Orthogonal range searching for text indexing.  In Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday, pages 267–302, 2013.  URL: https://doi.org/10.1007/978-3-642-40273-9_18, doi:10.1007/978-3-642-40273-9\\_18.
  * [24] Veli Mäkinen and Gonzalo Navarro.  Position-restricted substring searching.  In 7th Latin American Symposium on Theoretical Informatics, pages 703–714. Springer, 2006.
  * [25] Veli Mäkinen and Gonzalo Navarro.  Rank and select revisited and extended.  Theoretical Computer Science, 387(3):332–347, 2007.  doi:10.1016/j.tcs.2007.07.013.
  * [26] J. Ian Munro, Gonzalo Navarro, and Yakov Nekrich.  Text indexing and searching in sublinear time.  In 31th Annual Symposium on Combinatorial Pattern Matching, CPM 2020, July 17-19, 2020, Copenhagen, Denmark. To appear., 2020.
  * [27] J Ian Munro, Yakov Nekrich, and Jeffrey S Vitter.  Fast construction of wavelet trees.  Theoretical Computer Science, 638:91–97, 2016.
  * [28] Yakov Nekrich and Gonzalo Navarro.  Sorted range reporting.  In 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings, pages 271–282, 2012.  doi:10.1007/978-3-642-31155-0\\_24.
  * [29] Mihai Patrascu and Mikkel Thorup.  Time-space trade-offs for predecessor search.  In 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 232–240. ACM, 2006.
  * [30] Dan E. Willard.  New data structures for orthogonal range queries.  SIAM Journal on Computing, 14(1):232–253, 1985.  doi:10.1137/0214019.
  * [31] Chih-Chiang Yu, Wing-Kai Hon, and Biing-Feng Wang.  Improved data structures for the orthogonal range successor problem.  Computational Geometry, 44(3):148–159, 2011.  doi:10.1016/j.comgeo.2010.09.001.
  * [32] Gelin Zhou.  Two-dimensional range successor in optimal time and almost linear space.  Information Processing Letters, 116(2):171–174, 2016.  doi:10.1016/j.ipl.2015.09.002.

##  Appendix A Proofs Omitted From Section 2

###  A.1 Proof of Lemma 2.4

Through out the paper, we define $C(s..f)$ to be the bits between and
including the $s$\- and $f$-th most significant bits of $C$, where $C$ can be
an integer or a character. Our proof requires the following lemma:

######  Lemma A.1.

Let $C[0..n^{\prime}-1]$ be a packed sequence of $c$-bit elements, where
$n^{\prime}\leq n$. Given a pair of parameters $s$ and $f$ satisfying that
$0\leq s\leq f\leq c-1$, a packed sequence $A[0..n^{\prime}-1]$ of
$(f-s+1)$-bit elements in which $A[i]=C[i](s..f)$ for each entry
$i\in[0..n^{\prime}-1]$ can be constructed in $O(n^{\prime}{c}/{\lg n}+1)$
time.

######  Proof A.2.

Let $\delta$ denote the block size $\lfloor\frac{\lg n}{2\times c}\rfloor$. We
construct a universal lookup table $U$. For each possible $\delta$-element
packed sequence $S_{1}$ drawn from alphabet $[2^{c}]$, and each different
range $[s,f]$ where $0\leq s\leq f\leq c-1$, $U$ stores a packed sequence
$S_{2}$ in which $S_{2}[i]=S_{1}[i](s..f)$ for each $i\in[0..\delta-1]$. As
there are $2^{\delta\times c}\times c^{2}=\sqrt{n}\times c^{2}$ entries in
$U$, and each entry stores a result of $\delta\times(f-s+1)$ bits, table $U$
occupies $O(\sqrt{n}\times c^{2}\times\delta\times(f-s+1))=o(n)$ bits of
space. Given a pair of parameters $s$ and $f$, we can apply table $U$ to
extract the bits from $\delta$ consecutive elements
$C[i],C[i+1],\ldots,C[i+\delta-1]$ for each $i\in[0,n^{\prime}-1-\delta]$ in
constant time. Therefore, the overall processing time is $O(n^{\prime}{c}/{\lg
n}+1)$.

With this lemma, we now prove Lemma 2.4.

######  Proof A.3.

We only prove the result when value and index arrays are required; the other
results in the lemma follow by removing the steps of constructing them. The
construction consists of two steps: we first build a binary wavelet tree
$T_{2}$ and then convert it to a $d$-ary wavelet tree $T_{d}$.

To construct $T_{2}$, let $r$ denote its root node, and we have $A(r)=A$ and
$I(r)=I$. We then create the left child, $r_{0}$, and the right child,
$r_{1}$, of $r$, and perform a linear scan of $A(r)$ and $I(r)$. During the
scan, for each $i\in[0,|A(r)|-1]$, if the highest bit of $A(r)[i]$ is $0$,
then $A(r)[i]$ is appended to $A(r_{0})$, and $I(r)[i]$ is appended to
$I(r_{0})$. Otherwise, they are appended to $A(r_{1})$ and $I(r_{1})$.
Afterwards, we recursively process the child node $r_{0}$ and $r_{1}$ in the
same manner, but we examine the second highest bit of each element of
$A(r_{0})$ and $A(r_{1})$. In general, when generating the sequences for the
child nodes of an internal node $u$ at tree level $l$ where
$l\in[0,\lg\sigma-1]$, we append $A(u)[i]$ and $I(u)[i]$ to $A(r_{0})$ and
$I(r_{0})$, respectively, if the $l$-th highest bit of $A(u)[i]$ is 0.
Otherwise. they are appended to $A(r_{1})$ and $I(r_{1})$. If $A(v)$ for some
node $v$ is empty but $v$ is above the leaf level, then we keep $v$ as an
empty node, and at next phase we create empty children $v_{0}$ and $v_{1}$
under $v$. $T_{2}$ have been constructed completely after processing all the
$\lceil\lg\sigma\rceil$ bits of each element of $A$.

To speed up this process, we use a universal table $U$. Let
$b=\lfloor\frac{\lg n}{2t}\rfloor$, where $t=\lceil\lg
n^{\prime}\rceil+\lceil\lg\sigma\rceil$. This table $U$ has an entry for each
possible triple $(D,E,c)$, where $D$ is a sequence of length $b$ drawn from
universe $[\sigma]$, $E$ is a sequence of length $b$ drawn from universe
$[n^{\prime}]$, and $c$ is an integer in $[0,\lceil\lg\sigma\rceil-1]$. This
entry $U[D,E,c]$ stores four packed sequences $D_{0}$, $D_{1}$, $E_{0}$ and
$E_{1}$ defined as follows: $D_{0}[i]$ or $D_{1}[i]$ stores the $i$th element
in $D$ whose $c$-th most significant bit is $0$ or $1$, respectively, while
$E_{0}[i]$ or $E_{1}[i]$ stores $E[j]$ if $D[j]$ is the $i$th element in $A$
whose $c$-th most significant bit is $0$ or $1$, respectively. Similar to the
table $U$ in the proof of Lemma A.1, $U$ uses $o(n)$ bits. By performing table
lookups with $U$, we can process $b$ consecutive elements in $A(u)$ and $I(u)$
in constant time, and hence we spend $O(|A(u)|/b+1)$ time on each internal
node $u$. The sum of the lengths of all the value arrays for the nodes at the
same level of $T_{2}$ is $n^{\prime}$. As $T_{2}$ has
$\lceil\lg\sigma\rceil+1$ levels and $O(\sigma)$ nodes, the total time
required to construct $T_{2}$ is $O(n^{\prime}\lg\sigma(\lg
n^{\prime}+\lg\sigma)/{\lg n}+\sigma)$.

We then transform $T_{2}$ into a $d$-ary tree $T_{d}$. For simplicity, assume
that $\sigma$ is a power of $d$. We first remove the nodes of $T_{2}$ whose
levels are not multiples of $\lg d$, and add edges between each remaining node
$u$ and its descendants at the next remaining level. We then visit each
internal node $u$ of $T_{d}$ and associate it with a packed sequence $S(u)$
storing $A(u)[i](l\lg d..(l+1)\lg d-1)$ for all $i\in[0,|A(u)|-1]$, where $l$
is the level of $u$ in $T_{d}$. It remains to analyze the time needed to
transform $T_{2}$ into $T_{d}$. For each internal node $u\in T_{d}$, it takes
$O(|A(u)|\lg\sigma/\lg n+1)$ time to construct $S(u)$. The sum of the lengths
of all the value arrays for the nodes at the same level of $T_{d}$ is
$n^{\prime}$. As $T_{d}$ has $\lg\sigma/\lg d+1$ levels and $O(\sigma)$ nodes,
the time required to construct $S(u)$’s for all the internal node of $T_{d}$
is $O(n^{\prime}\lg^{2}\sigma/(\lg n\times\lg d)+\sigma)$. Therefore, the two
steps of our construction algorithm use $O(n^{\prime}\lg\sigma(\lg
n^{\prime}+\lg\sigma)/{\lg n}+\sigma)$ time in total.

###  A.2 Proof of Lemma 2.5

######  Proof A.4.

For simplicity, assume that $\sigma$ is a power of $d$. We use $O(n)$ time to
create a sequence $I[0..n-1]$ in which $I[i]=i$ for each $i\in[0..n-1]$. At
the root node $r$ of the wavelet tree, set $A(r)=A$ and $I(r)=I$. We then
create an empty sequence $S(r)$, and, for each $i\in[0,n^{\prime}-1]$, we
append $A(r)[i](0..\lg d-1)$ to $S(r)$. At the second level, there are $d$
children of $r$. We linearly scan $A(r)$, $I(r)$ and $S(r)$, appending
$A(r)[i]$ or $I(r)[i]$ to $A(r_{\alpha})$ or $I(r_{\alpha})$, respectively,
where $\alpha=S(r)[i]$ and $r_{\alpha}$ represents the $\alpha$-th child node
of $r$. Next, we construct $S(v)$ for each node $v$ at the second tree level
by appending $A(v)[i](\lg d..2\lg d-1)$ to $S(v)[i]$ for each
$i\in[0,|A(v)|-1]$.

This process continues at each successive level: in general, when generating
$S(u)$ for a node $u$ at a level $\ell$ where $\ell\in[0,\frac{\lg\sigma}{\lg
d}-1]$, we append $A(u)[i](\ell\times\lg d..(\ell+1)\times\lg d-1)$ to
$S(u)[i]$ for each $i\in[0,|A(u)|-1]$. If $u$ is an internal node, we append
$A(u)[i]$ or $I(u)[i]$ to the sequence $A(u_{\alpha})$ or $I(u_{\alpha})$,
respectively, where $\alpha=S(u)[i]$. After reaching the leaf level,
$\frac{\lg\sigma}{\lg d}+1$ levels have been created on $T_{d}$. As it uses
$O(n)$ time for the non-empty nodes at each tree level and there are in total
at most $O(\sigma)$ empty nodes, overall the construction time is
$O(n\times{\lg\sigma}/{\lg d}+\sigma)=O(n{\lg\sigma}/{\lg d})$, as $\sigma\leq
n$.

###  A.3 Proof of Lemma 2.7

Our proof requires the $\mathtt{count}_{c}(A,j)$ operation which computes the
number of elements less than or equal to $c$ in $A[0..j]$. Clearly the support
for $\mathtt{count}$ implies that for $\mathtt{rank}$. Our proof alos requires
the following lemma:

######  Lemma A.5 ([3, Lemma 2.3]).

Let $A[0..n^{\prime}-1]$ be a packed sequence drawn from alphabet $[\sigma]$,
where $n^{\prime}\leq n$ and $\sigma<\lg^{1/3}n$. A systematic data structure
occupying $o(n^{\prime})$ extra bits supporting $\mathtt{count}$ in $O(1)$
time can be constructed in $O(n^{\prime}\lg\sigma/\lg n)$ time.

With Lemma A.5, we now prove Lemma 2.7.

######  Proof A.6.

Lemma A.5 already subsumes this lemma when $\sigma\leq 2^{\lceil 1/4\lg\lg
n\rceil}$, so it suffices to assume that $2^{\lceil 1/4\lg\lg n\rceil}<\sigma$
in the rest of the proof.

Let $d=2^{\lceil 1/4\lg\lg n\rceil}$. We first build a $d$-ary wavelet tree
$T$ in $O(n^{\prime}\lg^{2}\sigma/{\lg n}+\sigma)$ time by Lemma 2.4. Then the
height of the tree is $h=O(\lg\sigma/(1/4\lg\lg n))=O(1)$. For each level $l$
of $T$ except the leaf level, we construct a packed sequence $S_{l}$ by
concatenating all the $S(v)$’s for the nodes at this level from left to right.
As $S_{l}$ is drawn from alphabet $[d]$ and there are at most $\sigma$ nodes
at each level, it takes $O(|S_{l}|\lg d/\lg
n+\sigma)=O(n^{\prime}\lg\sigma/\lg n+\sigma)$ time to construct $S_{l}$. We
then build a data structure $C_{l}$ with constant-time support for
$\mathtt{count}$ over $S_{l}$; by Lemma A.5, this data structure occupies
$o(n^{\prime}\lg\sigma)$ extra bits, and it can be constructed in
$O(n^{\prime}\lg d/\lg n)=O(n^{\prime}\lg\sigma/\lg n)$ time. At last, we
discard all sequences $S(v)$ and the tree $T$ to save space. As $T$ has a
constant number of levels, all the $S_{l}$’s and $C_{l}$’s occupy
$n^{\prime}\lceil\lg\sigma\rceil+o(n^{\prime}\lg\sigma)$ bits in total, and
their construction time, including that of $T$ which we discard later, is
$O(n^{\prime}\lg^{2}\sigma/{\lg n}+\sigma)$. The set of $S_{l}$’s and
$C_{l}$’s is the data structures Bose et al. [9, Theorem 4] designed, which
support $\mathtt{count}$ operations in constant time over a sequence drawn
from an alphabet of size $O(\operatorname{polylog}(n))$. This implies the
support for $\mathtt{rank}$.

###  A.4 Proof of Lemma 2.9

######  Proof A.7.

Belazzougui et al. [4, Lemma 3.5] already proved this lemma for the case in
which $\sigma\leq n$. When $\sigma>n$, then the data structure we construct is
simply an array $A^{\prime}[0..n-1]$ storing all the answers, i.e.,
$A^{\prime}[i]=\mathtt{rank^{\prime}}(A,i)$ for any $i\in[0,n-1]$.
$A^{\prime}$ occupies $O(n\lg n)=O(n\lg\sigma)$ bits. To construct
$A^{\prime}$, it is enough to perform a linear scan of $A$, and during the
scan, we maintain an array $C[0..\sigma-1]$ in which $C[j]$, for any
$j\in[0,\sigma-1]$, stores how many times symbol $j$ occurs in the portion of
$A$ that we have scanned so far. This uses $O(n+\sigma)$ time.

###  A.5 Proof of Lemma 2.11

Belazzougui and Puglisi [5] provided a systematic scheme with efficient
construction for range minimum/maximum queries over an input sequence from
small alphabets. Our proof requires their result presented as follows.

######  Lemma A.8 ([5, Lemma D.1]).

Let $A[0..n^{\prime}-1]$ be a packed sequence drawn from alphabet $[\sigma]$,
where $n^{\prime}\leq n$ and $\sigma\leq 2^{\sqrt{\lg n}}$. There is a
systematic data structure using $O(n^{\prime}{\lg\sigma}/{\lg n})$ extra bits
constructed in $O(n^{\prime}{\lg\sigma}/{\lg n})$ time, which answers
$\mathtt{rmq}(i,j)/\mathtt{rMq}(i,j)$ queries in constant time. The query
procedures each uses a universal table of $o(n)$ bits.

With Lemma A.8, we now prove Lemma 2.11:

######  Proof A.9.

If $\sigma\leq\lg n$, each element in $A$ can be encoded with $O(\lg\lg n)$
bits, so explicitly storing elements of $A$ requires $O(n^{\prime}\lg\lg n)$
bits, which is affordable. We then apply Lemma A.8 for
$\mathtt{rmq}/\mathtt{rMq}$ queries over $A$, which achieves the efficient
construction time and the constant query time. Therefore, for the rest of the
proof, it suffices to assume $\sigma>\lg n$.

We only show the proof for range minimum as the support for range maximum is
similar. Let $b$ denote the block size $\lfloor{\lg
n}/{(2\lg\lceil\sigma\rceil)}\rfloor$. The elements of $A$ are conceptually
divided into blocks of $b$ elements each. With a universal lookup table $U$,
we can retrieve the minimum value of a block of elements in constant time. For
each possible $b$ elements drawn from $[\sigma]$, $U$ stores the minimum
element value of these $b$ elements. Similar to the table $U$ in the proof of
Lemma A.1, $U$ uses $o(n)$ bits.

Next, we store the minimum values of the blocks in a sequence $A^{\prime}$
ordered by their original position in $A$. The sequence $A^{\prime}$ occupies
$O(n^{\prime}/b\times\lg\sigma)=O(n^{\prime})$ bits. Over $A^{\prime}$ we
build a data structure $DS_{1}$ of $O({n^{\prime}}/{b})$ bits in
$O({n^{\prime}}/{b})$ time by Lemma 2.10.

To save storage, we do not keep the original element values in a block.
Instead, each element value $e$ is replaced with its rank, i.e., the number of
elements in the block that are smaller than $e$. As each block has $b$
elements, the rank value can be encoded with $O(\lg b)=O(\lg\lg n)$ bits. The
transformation from element values to their corresponding rank values for each
block can be processed in constant time by applying a universal lookup table
$U^{\prime}$. For each possible $b$ elements drawn from
$\\{0,1,...,\sigma-1\\}$, we store the rank values in $O(b\lg\lg n)$ bits.
Similar to the table $U$ in the proof of Lemma A.1, $U^{\prime}$ uses $o(n)$
bits. With table $U^{\prime}$, we spend $O(\frac{n^{\prime}}{b})$ time on
transferring $n^{\prime}$ elements into their ranks.

At last, we construct a universal lookup table $U^{\prime\prime}$ in which for
each possible $b$ elements drawn from $[b]$ and for each different query range
$[q_{1},q_{2}]$ where $0\leq q_{1}\leq q_{2}\leq b-1$, we store the in-block
index of the minimum value in the range $[q_{1},q_{2}]$. Similar to the table
$U$ in the proof of Lemma A.1, $U^{\prime\prime}$ uses $o(n)$ bits. The
universal table $U^{\prime\prime}$ will be used amid the querying procedure
only.

All rank values occupy $O(n^{\prime}\lg\lg n)$ bits. In addition to the
$O(n^{\prime}+\frac{n^{\prime}}{b})$-bit space usage of $A^{\prime}$ and
$DS_{1}$, the overall space cost is $O(n^{\prime}\lg\lg n)$ bits. As shown
above, computing the rank value for all $n^{\prime}$ elements uses
$O(\frac{n^{\prime}}{b})$ time. Constructing the sequence $A^{\prime}$ and
building the data structure $DS_{1}$ over $A^{\prime}$ takes
$O(\frac{n^{\prime}}{b})$ time. Overall the construction time is bounded by
$O({n^{\prime}}/{b})=O(n^{\prime}\lg\sigma/\lg n)$.

Now we show how to answer the range minimum query given a query range $[i,j]$.
Let $B_{s}$ and $B_{t}$ denote the block containing $i$ and $j$, respectively,
where $s=\lfloor\frac{i}{b}\rfloor$ and $t=\lfloor\frac{j}{b}\rfloor$. We only
consider the case when $s<t$; the remaining case in which $s$ is equal to $t$
can be handled similarly. Let $m_{1}$ denote the minimum value in $B_{s}[i\
mod\ b,b-1]$, $m_{2}$ denote the minimum value among blocks $B_{s+1}$,
$B_{s+2}$,…, $B_{t-1}$, and $m_{3}$ denote the minimum value in $B_{t}[0,j\
mod\ b]$. The answer is clearly $\min(m_{1},m_{2},m_{3})$.

The value $m_{2}$ can be retrieved in constant time as follows: We search the
data structure $DS_{1}$ for the index $\tau$ of the minimum value in the query
range $[s+1,t-1]$ and complete with accessing $A^{\prime}[\tau]$. For the
values $m_{1}$ and $m_{3}$ both can be answered in a similar way, and we take
how to retrieve $m_{1}$ as an example. Given the pattern of block $B_{s}$ and
the query range $[i\ mod\ b,b-1]$, we can apply $U^{\prime\prime}$ to retrieve
the in-block index $\tau$ of the minimum value $e$ in constant time, compute
the original index $\tau^{\prime}$ of $e$ in $A$, where $\tau^{\prime}=b\times
s+\tau$, and retrieve $m_{1}$ by accessing $A[\tau^{\prime}]$. Overall, the
query requires $O(1)$ time and $O(1)$ accesses to the elements of $A$.

##  Appendix B Fast Construction of Predecessor Query Structures

Let $A[0..n-1]$ be a sequence of integers sorted in the increasing order.
Given a query integer $x$, we define operations $\mathtt{pred}(x)$ and
$\mathtt{succ}(x)$:

$\mathtt{pred}(x)=\max\\{j\ |\ A[j]\leq x,0\leq j\leq n-1\\}$
$\mathtt{succ}(x)=\min\\{j\ |\ x\leq A[j],0\leq j\leq n-1\\}$

Belazzougui et al. [4] show a data structure with deterministic linear
preprocessing time for predecessor/successor queries. Their result shown as
follows will be used later in our methods.

######  Lemma B.1 ([4, Lemma 3.6]).

Given a sorted sequence $A$ of integers from universe $[0,u-1]$, a data
structure of $O(n\lg u)$ bits can be constructed in linear time, which answers
a $\mathtt{pred}$ or $\mathtt{succ}$ query in $O(\lg\lg u)$ time.

We also need a solution under the indexing model over packed sequences. The
following result can be achieved by combining an approach of Grossi et al.
[18] with Lemma B.1, while applying universal tables.

######  Lemma B.2.

Given a sorted packed sequence $A$ of $n^{\prime}$ distinct integers from
$[\sigma]$, where $n^{\prime}\leq n$ and $\sigma\leq 2^{c\sqrt{\lg n}}$ for
any arbitrary positive constant $c$, a data structure using
$O(n^{\prime}\lg\lg\sigma)$ extra bits of space can be constructed in
$O({n^{\prime}}/{\sqrt{\lg n}})$ time, which answers a $\mathtt{pred}(x)$ or
$\mathtt{succ}(x)$ query in $O(\lg\lg\sigma)$ time and $O(1)$ accesses to the
elements of $A$. The construction and query procedures each requires access to
a universal table of size $o(n)$ bits.

######  Proof B.3.

Let $b=\lfloor\sqrt{\lg n}/(2c)\rfloor$. We divide $A$ into blocks of length
$b$ each. We retrieve the last element of each block and construct a
predecessor/successor data structure $R$ over these elements using Lemma B.1.
$R$ uses $O(({n^{\prime}}/{b})\times\lg\sigma)=O(n^{\prime})$ bits of space
and can be constructed in $O({n^{\prime}}/{b})$ time. Then, over each block,
we regard each integer in it as a binary string of length $\lg\sigma$ and
construct a Patricia trie over the integers in this block, as done by Grossi
et al. [18, Lemma 3.3]. This is a compressed bitwise trie with a skip value of
$O(\lg\lg\sigma)$ bits stored at each node. It stores elements at the leaves
in sorted order. As the trie has $b$ leaves and $b-1$ internal nodes, its tree
structure can be encoded in $O(b)$ bits. With skip values, each trie can be
encoded in $O(b\lg\lg\sigma)$ bits, without encoding the $b$ elements at its
leaves. To construct such a trie fast, we use a universal $U$ which has an
entry for any possible packed sequence $S$ of $b$ elements drawn from
$[\sigma]$. This entry stores the Patricia trie (without the elements stored
at leaves) of $O(b\lg\lg\sigma)$ bits constructed upon $S$. As there are at
most $2^{(\lg\sigma)\times b}\leq\sqrt{n}$ different entries in $U$, $U$ uses
$O(\sqrt{n}\times b\lg\lg\sigma)=o(n)$ bits. With $U$, a Patricia trie over
any block of $b$ elements can be constructed in constant time. As there are
$\lceil{n^{\prime}}/{b}\rceil$ blocks in total, the overall space usage of the
tries and $R$ is $O(({n^{\prime}}/{b})\times
b\lg\lg\sigma+n^{\prime})=O(n^{\prime}\lg\lg\sigma)$ bits, and and the overall
processing time is $O({n^{\prime}}/{\sqrt{\lg n}})$.

To answer a query, given an integer $y$, where $y\in[0,\sigma-1]$, we first
perform a predecessor or successor query over $R$ to find the block $B$
containing $\mathtt{pred}(y)$ or $\mathtt{succ}(y)$ in $O(\lg\lg\sigma)$ time.
Then, with the help of an $o(n)$-bit universal table, we query over the trie
built upon $B$ using the query algorithm by Grossi et al. [18] in $O(1)$ time
and $O(1)$ accesses of elements of $A$ to retrieve $\mathtt{pred}(y)$ or
$\mathtt{succ}(y)$. Therefore, the overall query cost is $O(\lg\lg\sigma)$
time and $O(1)$ accesses to elements of $A$.

We then extend Lemma B.2 for a sequence of integers that are not necessarily
distinct.

######  Lemma B.4.

Given a sorted packed sequence $A$ of $n^{\prime}$ integers from $[\sigma]$,
where $n^{\prime}\leq\sigma\leq 2^{c\sqrt{\lg n}}$ for any arbitrary positive
constant $c$, a data structure using $O(n^{\prime}\lg\lg\sigma)$ extra bits of
space can be constructed in $O({n^{\prime}}/{\sqrt{\lg n}})$ time, which
answers a $\mathtt{pred}(x)$ or $\mathtt{succ}(x)$ query in $O(\lg\lg\sigma)$
time and $O(1)$ accesses to the elements of $A$. The construction and query
procedures each requires access to a universal table of size $o(n)$ bits.

######  Proof B.5.

We create a bitvector $B[0..n^{\prime}]$ in which $B[i]=1$ if $i=0$ or
$A[i]>A[i-1]$, and represent it by Lemma 2.8 to support $\mathtt{rank}$ and
$\mathtt{select}$. Thus $B$ records the position of the first occurrence of
each distinct integer in $A$. We also define a sequence $A^{\prime}[0..t-1]$,
in which $A^{\prime}[i]=A[\mathtt{select}_{1}(B,i)]$, where $t$ is the number
of distinct elements in $A$. $A^{\prime}[0..t-1]$ then stores the distinct
elements of $A$. We construct a predecessor/successor structure over
$A^{\prime}$ using Lemma B.2. $A^{\prime}$ is needed during construction but
is discarded at the end of preprocessing, as each element, $A^{\prime}[i]$,
can be accessed by retrieving $A[\mathtt{select}_{1}(B,i)]$. By Lemmas 2.8 and
B.2, $B$ and the predecessor/successor structure over $A^{\prime}$ occupy
$O(n^{\prime}\lg\lg\sigma)$ bits in total.

Next, we give a query algorithm for $\mathtt{succ}(x)$ over $A$; the support
for $\mathtt{pred}(x)$ is similar. We perform a successor query over
$A^{\prime}$ to retrieve the successor, $x^{\prime}$, in $A^{\prime}$, which
uses $O(\lg\lg\sigma)$ time and $O(1)$ accesses of elements of $A$. This will
also give the position, $i$, of $x^{\prime}$ in $A^{\prime}$. Then, we find
$\mathtt{succ}(x)$ over $A$ in constant time, which is
$\mathtt{select}_{1}(B,i)$. Overall, we require $O(\lg\lg\sigma)$ time and
$O(1)$ accesses of elements of $A$.

To build these data structures, we first show how to compute $B$ and
$A^{\prime}$. Let $b=\lfloor\sqrt{\lg n}/(2c)\rfloor$. We use a universal
table $U$ to generate $b$ elements of $B$ and $A^{\prime}$ in constant time.
$U$ has an entry for each possible packed sequence $S[0..b-1]$ drawn from
$[\sigma]$ and each possible flag $f\in\\{0,1\\}$, which stores a bitvector
$V[0..b-1]$ and a packed sequence $S^{\prime}$ of length at most $b$ defined
as follows: If $f=1$, we set $V[0]=1$ and $V[0]=0$ otherwise. For each
$i\in[1,b-1]$, if $S[i-1]=S[i]$, then $V[i]$ is set to 0. Otherwise, $V[i]$ is
set to 1. Then, the length of $S^{\prime}$ is equal to the number of $1$’s in
$V$, and $S^{\prime}[i]=S[\mathtt{rank}_{1}(V,i)]$. As $U$ has $O(n^{1/2})$
entries each using $O(\operatorname{polylog}(n))$ bits, $U$ occupies $o(n)$
bits. With $U$, we can generate $b$ bits in $B$ and $b$ entries of
$A^{\prime}$ in one table lookup, and thus the content of $B$ and $A^{\prime}$
can be computed in $O(n/b)$ time. Adding the construction time needed to build
query structures over them, the overall preprocessing time is
$O(n/b)=O({n^{\prime}}/{\sqrt{\lg n}})$.

For general integer sequences, we will use the
$\mathtt{pred}(x)/\mathtt{succ}(x)$ data structure by Chan et al. [11], which
is summarized in the following lemma (even though Chan et al. did not analyze
the construction time, it follows directly from previous results on the data
structure components used):

######  Lemma B.6 ([11, Section 2]).

Given an increasingly sorted sequence $A$ of $n^{\prime}$ distinct integers
from universe $[n]$ where $n^{\prime}\leq n$, a data structure using extra
$O(n^{\prime}\lg\lg n)$ bits of space can be constructed in linear time, which
answers a $\mathtt{pred}(x)$ or $\mathtt{succ}(x)$ query in $O(\lg\lg n)$ time
and $O(1)$ accesses to elements of $A$. The query algorithm requires access to
a universal table of $o(n)$ bits.

##  Appendix C Proofs Omitted From Section 3

###  C.1 Fast Construction of Sequence $M$

We show how to create $M$ efficiently with the help of a universal table $U$.
This table has an entry for each possible pair $(D,t)$, where $D$ is a
sequence of length $b=\lfloor\frac{\lg n}{2\lceil\lg\sigma\rceil}\rfloor$
drawn from $[\sigma]$ and $t$ is an integer in $[0,b]$. If $t=0$, this entry
stores a sequence of length $b$ which is obtained by appending a $1$-bit to
the end of the binary expression of each element in $D$. Otherwise, this entry
stores a sequence of length $b+1$ consisting of three sections: the first
section is obtained by appending a $1$-bit to the end of the binary expression
of each of the first $t$ elements in $D$, the second section is a boundary
element, and the third section is obtained by appending a $1$-bit to the end
of the binary expression of each of the last $b-t$ elements in $D$. As there
are at most $n^{1/2}$ possible sequences of length $b$ drawn from $\sigma$ and
$t$ has $b+1$ possible values, $U$ has at most $n^{1/2}(b+1)$ entries. Since
each entry is encoded in at most
$(b+1)(\lceil\lg\sigma\rceil+1)=O(\operatorname{polylog}(n))$ bits, $U$ uses
$o(n)$ bits. With $U$, we can scan $A$ and process $b$ of its elements in
constant time; whether or where a boundary element should be created when
processing these $b$ elements can be inferred by keeping track of the number
of elements of $b$ that we have scanned so far. Note that at most one boundary
element will be created when reading $b$ elements from $A$ as $b<\lg
n<\sigma$. The time needed to create $M$ is hence
$O(n^{\prime}/b)=O(n^{\prime}\lg\sigma/\lg n)$.

###  C.2 Processing $M(u)$ Efficiently with $U^{\prime}$

We show how to process $M(u)$ efficiently with the help of a universal table
$U^{\prime}$. Recall that $b=\lfloor\frac{\lg
n}{2\lceil\lg\sigma\rceil}\rfloor$. $U^{\prime}$ has an entry for each
possible pair $(E,c)$, where $E$ is a sequence of length $b$ drawn from
universe $[2\sigma]$ and $c$ is an integer in $[0,\lceil\lg\sigma\rceil-1]$.
This entry stores a pair of packed sequences $E_{0}$ and $E_{1}$ defined as
follows: $E_{0}$ or $E_{1}$ stores the boundary elements in $E$ and the
regular elements in $E$ whose $c$-th most significant bit is $0$ or $1$,
respectively. The elements in $E_{0}$ retain their relative order in $E$, and
the same is true with $E_{1}$. As $U^{\prime}$ has
$2^{b\times(\lceil\lg\sigma\rceil+1)}\times\lceil\lg\sigma\rceil$ entries and
each entry stores a pair of packed sequences occupying
$O(b\lceil\lg\sigma\rceil)$ bits in total, $U^{\prime}$ uses $o(n)$ bits. With
$U^{\prime}$, we can process $M(u)$ in $O(|M(u)|\lg\sigma/\lg n+1)$ time.

###  C.3 Constructing Sequences $P_{0},P_{1},\ldots,P_{\sigma-1}$

######  Lemma C.1.

Sequences $P_{0},P_{1},\ldots,P_{\sigma-1}$ can be constructed in
$O(n^{\prime}{\lg^{2}\sigma}/{\lg n}+\sigma)$ time in total.

######  Proof C.2.

The construction consists of two phases. In the first phase, we compute the
set of pairs $R_{k}=\\{(i,\mathtt{rank^{\prime}}(A_{k},i))|0\leq
i\leq\sigma-1\\}$ for each chunk $A_{k}$. Even though
$P_{i}[k]=\mathtt{rank^{\prime}}(A_{k},i)$ and thus the entries of all the
$P_{i}$’s have been computed in this phase, the pairs themselves generated for
$A_{k}$ are not in any order that allows us to directly assign values from
these pairs to entries of $P_{i}$’s quickly enough. Thus, in the second phase,
we reorganize all $n^{\prime}$ pairs computed from all the chunks, to compute
$P_{0},P_{1},\ldots,P_{\sigma-1}$ efficiently.

We first show how to compute the pair set $R_{k}$ for each $A_{k}$
efficiently. Let $I[0,\sigma-1]$ denote a packed sequence such that $I[i]=i$
for each $i\in[0,\sigma-1]$. Note that $I$ can be constructed once in
$O(\sigma)$ time and shared with all chunks. By Lemma 2.4, a binary wavelet
tree, in which node $u$ is associated with $A(u)$ and $I(u)$ as defined
before, over $A_{k}$ could be constructed in $O(\sigma\lg^{2}\sigma/\lg
n+\sigma)$ time. However, the second term $O(\sigma)$, when summed over all
$n^{\prime}/\sigma$ chucks, is too expensive to afford. Thus, we modify the
structure of a wavelet tree to decrease this term. In the modified tree, when
a node $v$ satisfies $|A(v)|\leq b=\lfloor\frac{\lg
n}{2\lceil\lg\sigma\rceil}\rfloor$, we make $v$ a leaf node without any
descendants. With this modification, we observe the following two properties.
First, if a leaf node $l$ satisfies $|A(l)|>b$, then the tree level of $l$
must be $\lg\sigma$ and all entries of $A(l)$ store the same symbol. Second,
as there are at most $\lceil\sigma/b\rceil$ nodes at each level, the modified
tree has $O(\sigma/b\times\lg\sigma)=O(\sigma\lg^{2}\sigma/\lg n)$ nodes.
Following from the analysis of the algorithm in the proof of Lemma 2.4, the
modified tree can be constructed in $O(\sigma\lg^{2}\sigma/\lg n)$ time. After
this tree is constructed, we only keep the sequences $A(l)$ and $I(l)$ for
each leaf node $l$ and call them leaf sequences. We discard the rest of the
tree.

To further compute $R_{k}$ using these leaf sequences, observe that, for any
symbol $\alpha$, there exists one leaf $l$ such that $A(l)$ contains all the
occurrences of $\alpha$ in $A$. Thus
$(I(l)[i],\mathtt{rank^{\prime}}(A_{k},I(l)[i]))=(I(l)[i],\mathtt{rank^{\prime}}(A(l),i))$
holds, which we can use to reduce the problem of computing the pairs in
$R_{k}$ to the problem of computing the answer to a partial rank query at each
position of $A(l)$ for each leaf $l$. Hence for each leaf $l$, we define a
packed sequence $Q(l)[0..|A(l)|-1]$ in which
$Q(l)[i]=\mathtt{rank^{\prime}}(A(l),i)$ to store these answers. To construct
$Q(l)$ efficiently, we consider two cases. When $|A(l)|\leq b$, we apply a
universal table $U^{\prime\prime}$ to generate $Q(l)$ in constant time.
$U^{\prime\prime}$ has an entry for each possible pair $(F,x)$, where $F$ is a
sequence of length $b$ drawn from universe $[\sigma]$, and $x$ is an integer
in $[0,b]$. This entry stores a packed sequence $G[0..x]$ in which
$G[i]=\mathtt{rank^{\prime}}(F,i)$. Similar to $U$ in Appendix C.1,
$U^{\prime\prime}$ uses $o(n)$ bits. When $|A(l)|>b$, all entries of $A(l)$
store the same symbol. Thus, we have $Q(l)[i]=i$ for each $i\in[0,|A(l)|-1]$,
and hence we can create $Q(l)$ by copying the first $|A(l)|$ elements from the
sequence $I$ which we created before. In either case, $Q(l)$ can be
constructed in $O(|A(l)|\lg\sigma/\lg n+1)$ time. Let $l_{i}$ denote the
$(i+1)$-st leaf visited in a preorder traversal of the tree, and $f$ the
number of leaves. Since $\sum_{i=0}^{f}|Q(l_{i})|=\sigma$ and
$f=O(\sigma\lg^{2}\sigma/\lg n)$, the total time required to build
$Q(l_{0}),Q(l_{1}),\ldots,Q(l_{f-1})$ is $O(\sigma\lg^{2}\sigma/\lg n)$. Then
we construct the concatenated packed sequence $I_{k}=I(l_{0})I(l_{1})\ldots
I(l_{f-1})$ and $Q_{k}=Q(l_{0})Q(l_{1})\ldots Q(l_{f-1})$. It requires
$O(\sigma\lg^{2}\sigma/\lg n)$ to concatenate these sequences if we process
$\Theta(\lg n)$ bits, i.e., $O(1)$ words, in constant time by performing bit
operations. Since for any $i\in[0,\sigma-1]$, $(I_{k}[i],Q_{k}[i])$ is a
distinct pair in $R_{k}$, $I_{k}$ and $Q_{k}$ store all the pairs in $R_{k}$.
We perform the steps in this and the previous paragraphs for all the chunks in
$A$, and the total time spent in this phase is
$O(n^{\prime}{\lg^{2}\sigma}/{\lg n}+\sigma)$.

Next we construct $P_{0},P_{1},\ldots,P_{\sigma-1}$ efficiently using the
pairs computed in the previous phase. We first build in
$O(n^{\prime}\lg^{2}\sigma/\lg n)$ time two concatenated packed sequences each
of length $n^{\prime}$: $I^{\prime}=I_{0}I_{1}\ldots I_{n^{\prime}/\sigma-1}$
and $Q=Q_{0}Q_{1}\ldots Q_{n^{\prime}/\sigma-1}$. Then we construct a binary
wavelet tree over $I^{\prime}$. Each node, $u$, of the wavelet tree is
associated with two sequences, $I^{\prime}(v)$ which contains all the elements
of $I^{\prime}$ whose values are within the range represented by $v$,
retaining their relative order in $I^{\prime}$, and $Q(v)$ in which $Q(v)[i]$
is the element in $Q$ corresponding to $I^{\prime}(v)[i]$. The algorithm of
constructing a binary wavelet tree shown in Lemma 2.4 can be modified easily
to construct this wavelet tree in $O(n^{\prime}\lg^{2}\sigma/\lg n+\sigma)$
time. Let $l^{\prime}_{i}$ denote the $(i+1)$st leaf of this wavelet tree in
preorder. Observe that all the entries in $I^{\prime}(l^{\prime}_{i})$ store
$i$, and $I^{\prime}(l^{\prime}_{i})[j]$ initially came from $A_{j}$, i.e.,
$I^{\prime}(l^{\prime}_{i})[j]$ corresponds to the $i$th position in chunk
$A_{j}$. Therefore, $Q(l^{\prime}_{i})[j]=P_{i}[j]$, and we have
$P_{i}=Q(l^{\prime}_{i})$. The processing time required for this phase is also
$O(n^{\prime}{\lg^{2}\sigma}/{\lg n}+\sigma)$, which is the same as the bound
for the first phase. Therefore, the total time required to construct all
sequences $P_{0},P_{1},\ldots,P_{\sigma-1}$ is
$O(n^{\prime}{\lg^{2}\sigma}/{\lg n}+\sigma)$.

###  C.4 Space Analysis of Data Structure in Lemma 3.5

######  Lemma C.3.

The structures built in Lemma 3.5 occupy
$n^{\prime}\lg\sigma+o(n^{\prime}\lg\sigma)$ extra bits of space.

######  Proof C.4.

In $B_{c}$, each $1$ bit corresponds to an occurrence of symbol $c$ in $A$,
while each $0$ corresponds to a chunk. Thus, these bit vectors have
$n^{\prime}$ $1$s and $n^{\prime}/\sigma\times\sigma=n^{\prime}$ $0$s in
total. Therefore, the lengths of all these bit vectors sum up to
$2n^{\prime}$. By Lemma 2.8, $o(n^{\prime})$ bits are needed to augment them
to support $\mathtt{rank}$ and $\mathtt{select}$. As each chunk has $\sigma$
elements, encoding an entry of each $P_{c}$ requires $\lceil\lg\sigma\rceil$
bits. Thus $P_{0}$, …, $P_{\sigma-1}$ occupy $n^{\prime}\lceil\lg\sigma\rceil$
bits in total. The total space usage of all the data structures in this
section is therefore
$2n^{\prime}+o(n^{\prime})+n^{\prime}\lceil\lg\sigma\rceil$ bits, which is
$n^{\prime}\lg\sigma+o(n^{\prime}\lg\sigma)$ when $\sigma>\lg n$.

##  Appendix D Proofs Omitted From Section 4

We first discuss how to construct the ball inheritance structures of Chan et
al. [11] efficiently over generalized wavelet trees, by replacing some of
their data structure components with those we designed in previous sections to
achieve faster construction time.

When used to represent the point set $N$, each node, $u$, of $T$ is
conceptually associated with an ordered list, $N(u)$, of points whose
$x$-coordinates are within the range represented by $u$, and these points are
ordered by $y$-coordinate. To save space, Chan et al. [11] do not encode each
ordered point list explicitly. Instead, they define a sequence,
$\mathit{S\\!p}(u)$, of skipping pointers for $u$, in which
$\mathit{S\\!p}(u)[i]$ stores, at a certain number of levels below $u$, which
descendant of $u$ has $N(u)[i]$ in its ordered list of points; different
choices of the distance between $u$ and its descendant give different time-
space tradeoffs. Then, since both $N(u)$ and $N(\mathit{S\\!p}(u)[i])$ order
points by $y$-coordinate, the result of a
$\mathtt{rank^{\prime}}(\mathit{S\\!p}(u),i)$ query is the position of the
point $N(u)[i]$ in $N(\mathit{S\\!p}(u)[i])$. Thus, to compute
$\mathtt{point}(v,i)$, we can follow these skip pointers starting from $v$ and
perform $\mathtt{rank^{\prime}}$ queries along the way, until we reach the
leaf level of $T$. As Chan et al. store the coordinates of each point in the
ordered lists associated with the leaves, this process will answer
$\mathtt{point}(v,i)$.

The following lemma gives analyses of the approach of Chan et al. [11], in
which the analysis of preprocessing time is restricted to the special cases
that we need for orthogonal range searching problems.

######  Lemma D.1.

Let $X[0..n^{\prime}-1]$ be a sequence drawn from alphabet $[\sigma]$ and
$Y[0..n^{\prime}-1]$ be a sequence in which $Y[i]=i$ for each
$i\in[0..n^{\prime}-1]$, where $max(\sigma,n^{\prime})\leq n$. A $d$-ary
wavelet tree over $X$, where $d$ is a power of $2$ upper bounded by $\sigma$,
can be represented using
$O(n^{\prime}\tau(\lg\sigma)\log_{\tau}(\log_{d}\sigma)+n^{\prime}\lg
n^{\prime}+\sigma w)$ bits to support $\mathtt{point}$ in
$O(\log_{\tau}(\log_{d}\sigma))$ time. Given $X$ and $Y$ as input, this tree
can be constructed in $O(n^{\prime}\tau\lg^{2}\sigma/\lg n+n^{\prime}\lg
n^{\prime}\lg\sigma/\lg n+\sigma\log_{d}\sigma)$ time if
$\sigma=O(2^{O(\sqrt{\lg n})})$. If $d\geq 2^{\sqrt{\lg n}}$, the construction
time is $O((n^{\prime}+\sigma)\log_{d}\sigma)$. The construction requires a
universal table of $o(n)$ bits. Given $X$ and $Y$ as input, a $d$-ary wavelet
tree over $X$ using
$O(n^{\prime}\tau(\lg\sigma)\log_{\tau}(\log_{d}\sigma)+n^{\prime}\lg
n^{\prime}+\sigma w)$ bits of space can be constructed in $P(n)$ time to
support $\mathtt{point}$ in $O(\log_{\tau}(\log_{d}\sigma))$ time, where (a)
$P(n)=O(n^{\prime}\tau(\lg^{2}\sigma/\lg n)+\sigma\log_{d}\sigma)$ if
$\sigma=O(2^{O(\sqrt{\lg n})})$, (b)
$P(n)=O(n^{\prime}\log_{d}\sigma+n^{\prime}\tau\lg\sigma/\sqrt{\lg
n}+\sigma\log_{d}\sigma)$ if $\sigma=\Omega(2^{O(\sqrt{\lg n})})$ and
$d<2^{\sqrt{\lg n}}$, 222In this case, it is possible to further decrease the
first term in $P(n)$ by combining a wavelet tree construction algorithm and
integer sorting, but we do not go into details since this case is never
encountered in our solutions to orthogonal range reporting/successor. (c)
$P(n)=O((n^{\prime}+\sigma)\log_{d}\sigma)$, if $\sigma=\Omega(2^{O(\sqrt{\lg
n})})$ and $d\geq 2^{\sqrt{\lg n}}$.

######  Proof D.2.

Let $h$ denote $\log_{d}\sigma$. Each point in $N$ appears in the ordered
point list associated with a node $u$ at each level, $l$, of $T$. At each
internal node, a skipping pointer is created, which encodes the rank of the
descendant of $u$ among all the descendants of $u$ at level
$l^{\prime}=\tau^{c+1}\lceil l/\tau^{c+1}\rceil$. As $u$ has
$d^{l^{\prime}-l}\leq d^{\tau^{c+1}}$ descendants at level $l^{\prime}$,
$\mathit{S\\!p}(v)[i]$ can be encoded using at most $\tau^{c+1}\lg d$ bits.
Since there are at most $h/\tau^{c}$ levels with color $c$, the skipping
pointers created for this point across all levels of $T$ occupy at most
$\sum_{c=0}^{\log_{\tau}h-1}\frac{h}{\tau^{c}}\times\tau^{c+1}\times\lg
d=O(\tau\lg\sigma\log_{\tau}h)$ bits. As there are $n^{\prime}$ points in $N$,
the space usage of all skipping pointers is
$O(n^{\prime}\tau\lg\sigma\log_{\tau}h)=O(n^{\prime}\tau(\lg\sigma)\log_{\tau}(\log_{d}\sigma))$
bits. By either Lemma 3.5 or Lemma 2.9, the extra space cost needed to build
data structures to support $\mathtt{rank^{\prime}}$ in sequences of skip
pointers is also $O(n^{\prime}\tau(\lg\sigma)\log_{\tau}(\log_{d}\sigma))$
bits. We know that there are in total $n^{\prime}$ points at the leaf level
and the coordinates of each point can be encoded in $O(\lg\sigma+\lg
n^{\prime})$ bits. So the cost of storing point coordinates at leaf levels is
$O(n^{\prime}(\lg\sigma+\lg n^{\prime}))$ bits. As $T$ has $O(\sigma)$ nodes,
the implicit representation of $T$, with color and depth information, occupies
$O(\sigma w)$ bits. Overall, the space usage of these structures is
$O(n^{\prime}\tau(\lg\sigma)\log_{\tau}(\log_{d}\sigma)+n^{\prime}\lg
n^{\prime}+\sigma w)$ bits.

Now we analyze the query time of $\mathtt{point}$. We retrieve the depth, $l$,
of $v$ to get the color, $c$, assigned to level $l$. If $v$ is a leaf node,
i.e., $c=\log_{\tau}h$, then $N(v)$ is stored explicitly, and we return
$N(v)[i]$ as the answer. Otherwise, let $l^{\prime}=\tau^{c+1}\lceil
l/\tau^{c+1}\rceil$. Then the point $p$ that we will eventually return as the
answer to the query is also distributed to the ordered point list associated
with the $\mathit{S\\!p}(v)[i]$-th descendant, $u$, of $v$ at level
$l^{\prime}$. Node $u$ can be located in constant time using the implicit
representation of $T$ as a complete $d$-ary tree. Furthermore, $p$ is at
position $j=\mathtt{rank^{\prime}}(\mathit{S\\!p}(v),i)$ of $N(u)$. We then
perform the query $\mathtt{point}(u,j)$ recursively to compute the answer. To
bound the running time, observe that this process is terminated once we reach
a leaf level. Hence, the process is applied recursively $O(\log_{\tau}h)$
times, each with a cost of $O(1)$. Therefore, it requires $O(\log_{\tau}h)$
time to support $\mathtt{point}(v,i)$.

To construct these data structures, we first build $T$ as a $d$-ary wavelet
tree $T$ over $X$ with value and index arrays. If $\sigma=O(2^{\sqrt{\lg
n}})$, $T$ can be built in $O(n^{\prime}{\lg\sigma(\lg
n^{\prime}+\lg\sigma)}/{\lg n}+\sigma)$ time by Lemma 2.4. Otherwise, it takes
$O(n^{\prime}\log_{d}\sigma+\sigma)$ time using the algorithm shown in Lemma
2.5. Computing the depth of each node of $T$ and storing $T$ implicitly use
$O(\sigma)$ time. We then assign colors to its levels as follows: We first
assign color $0$ to the root level. Then we assign color $\log_{\tau}h$ to the
leaf level. Among the remaining levels, we assign color $\log_{\tau}h-1$ to
those that are multiples of $\tau^{\log_{\tau}h-1}=h/\tau$, and so on. During
this process, an array of flags is used to mark those levels that have been
assigned colors. As we use $O(1)$ time for each level, this requires
$O(\log_{d}\sigma)$ time. Observe that the value and index arrays of each node
$u$ of $T$ encode the $x$\- and $y$-coordinates of the points in $N(u)$,
respectively. Therefore, at the leaf level, we keep its value and index arrays
as the encoding of $N(u)$. Otherwise, let $c$ be the color assigned to level
$l$. Then, for any $i\in[0,|N(u)|-1]$, $\mathit{S\\!p}(u)[i]$ needs to store
the rank of the descendant of $u$ at level $l^{\prime}=\tau^{c+1}\lceil
l/\tau^{c+1}\rceil)$, which can be computed as $A(u)[i](l\lg d..l^{\prime}\lg
d)$; recall that $A(u)$ is the value array of $u$ storing the $x$-coordinates
of the points in $N(u)$. By Lemma A.1, all elements of $\mathit{S\\!p}(u)$ can
be generated in $O(|N(u)|{\lg\sigma}/{\lg n}+1)$ time. The overall time needed
to generate all the skipping pointers across the entire tree $T$ is thus
bounded by $O(n^{\prime}{\lg^{2}\sigma}/({\lg n}\times\lg d)+\sigma)$, which
is subsumed by the time cost spending on building $T$. We discard the value
and index arrays of $u$ after $\mathit{S\\!p}(u)$ has been built.

Next, we show how to build the data structure for $\mathtt{rank^{\prime}}$
queries upon $\mathit{S\\!p}(u)$. We first consider the case in which
$\sigma=O(2^{\sqrt{\lg n}})$, in which the alphabet size of
$\mathit{S\\!p}(u)$ is at most $\sigma=O(2^{\sqrt{\lg n}})$, so we apply Lemma
3.5 to build a $\mathtt{rank^{\prime}}$ structure over $S(u)$.
$\mathit{S\\!p}(u)$ is drawn from alphabet $d^{l^{\prime}-l}$, and since
$l^{\prime}-l\leq\tau^{c+1}$, this structure can be built in
$O(|\mathit{S\\!p}(u)|(l^{\prime}-l)^{2}\lg^{2}d/\lg
n+d^{l^{\prime}-l})=O(|\mathit{S\\!p}(u)|\tau^{2c+2}\lg^{2}d/\lg
n+d^{l^{\prime}-l})$ time. Over all nodes at level $l$, observe that the term,
$|\mathit{S\\!p}(u)|\tau^{2c+2}\lg^{2}d/\lg n$, sums up to
$n^{\prime}\tau^{2c+2}\lg^{2}d/\lg n$, while the term, $d^{l^{\prime}-l}$,
sums up to $f\times d^{l^{\prime}-l}$, where $f$ is the number of nodes at
level $l$. To bound $f$, observe that, as each node at level $l$ has
$d^{l^{\prime}-l}$ descendants, there are $f\times d^{l^{\prime}-l}$ nodes at
level $l^{\prime}$ and we have $f\times d^{l^{\prime}-l}\leq\sigma$. Thus the
sum of the term, $d^{l^{\prime}-l}$, over nodes at level $l$ is bounded by
$\sigma$. Hence the total time required to build auxiliary data structures for
$\mathtt{rank^{\prime}}$ for nodes at a level with color $c$ is
$O(n^{\prime}\tau^{2c+2}\lg^{2}d/\lg n+\sigma)$. As there are at most
$h/\tau^{c}$ levels with color $c$, the total construction time over all
levels of $T$, including the time spent building and coloring $T$ itself, is
$O(n^{\prime}{\lg\sigma(\lg n^{\prime}+\lg\sigma)}/{\lg
n}+\sigma+\sum_{c=0}^{(\log_{\tau}h)-1}(h/\tau^{c})\times
O(n^{\prime}\tau^{2c+2}\lg^{2}d/\lg
n+\sigma)=O(n^{\prime}\tau\lg^{2}\sigma/\lg n+n^{\prime}\lg
n^{\prime}\lg\sigma/\lg n+\sigma\log_{d}\sigma)$. Finally, we consider the
case in which $d\geq 2^{\sqrt{\lg n}}$. In this case, all
$\mathtt{rank^{\prime}}$ structures are built using Lemma 2.9, so the total
construction time is
$O(n^{\prime}\log_{d}\sigma+\sigma)+\sum_{c=0}^{(\log_{\tau}h)-1}O(n^{\prime}+\sigma)=O(n^{\prime}\log_{d}\sigma+\sigma\log_{d}\sigma)$.

Another operation of ball inheritance is $\mathtt{noderange}(c,d,v)$. Recall
that given a range $[c,d]$ and a node $v$ of $T$, $\mathtt{noderange}(c,d,v)$
finds the range $[c_{v},d_{v}]$ such that $I(v)[i]\in[c,d]$ iff
$i\in[c_{v},d_{v}]$. Obviously, $c_{v}$ or $d_{v}$ is equal to the positions
of $\mathtt{succ}(c)$ or $\mathtt{pred}(d)$ in $I(v)$, respectively. Hence by
constructing predecessor/successor data structures over $I(v)$, we can support
$\mathtt{noderange}$.

Lemmas 4.1 and 4.2 addressing special cases of ball inheritance, in which
either the wavelet tree has high fanout or the coordinates can be encoded in
$O(\sqrt{\lg n})$ bits, can thus be obtained by choosing appropriate values
for $\tau$ and applying different data structures for
$\mathtt{pred}$/$\mathtt{succ}$ operations. Next, we give the proofs of these
Lemmas.

###  D.1 Proof of Lemma 4.1

######  Proof D.3.

Consider the case in Lemma D.1 for $d\geq 2^{\sqrt{\lg n}}$. In this case, set
$n^{\prime}=n$ and $d=2^{\sqrt{\lg n}}$. By further setting $\tau=2$ or
$\tau=\lg^{\epsilon}\sigma$, we have the result $(a)$ or $(b)$, respectively,
apart from the support of $\mathtt{noderange}$. Next, we show the data
structure supporting $\mathtt{noderange}$, whose space cost and construction
time are both subsumed by the data structure supporting $\mathtt{point}$. We
apply Lemma B.6 to construct a data structure supporting
$\mathtt{pred}/\mathtt{succ}$ over $I(v)$ at each node $v$, which answers
$\mathtt{noderange}$ in $O(\lg\lg n)$ time and $O(1)$ calls to
$\mathtt{point}$ without requiring $I(v)$ to be stored explicitly. This
structure occupies $O(|I(v)|\lg\lg n)$ extra bits of space can be built upon
$I(v)$ in $O(|I(v)|)$ time. As $T$ has $\lg\sigma/\sqrt{\lg n}+1$ levels and
there are $n$ elements at each level, the overall time needed to construct it
over all nodes is $O(n\lg\sigma/\sqrt{\lg n})$, and the overall extra space
cost is $O(n\lg\lg n\times\lg\sigma/\sqrt{\lg n})=o(n\lg\sigma)$ bits.

###  D.2 Proof of Lemma 4.2

When coordinates of points can be encoded in $O(\sqrt{\lg n})$ bits, we can
achieve faster construction time by applying the $\mathtt{rank^{\prime}}$
supporting data structure designed in Lemma 3.5 and the
$\mathtt{pred}/\mathtt{succ}$ supporting data structure under the indexing
model designed in Lemma B.4.

######  Proof D.4.

Consider the case in Lemma D.1 for $\sigma=O(2^{O(\sqrt{\lg n})})$. By setting
$\tau=2$ and applying $n^{\prime}=O(\sigma^{O(1)})$, we can obtain the
construction time, the space cost and the query time needed to support
$\mathtt{point}$, which match the bounds show in this lemma. It remains to
show the support of $\mathtt{noderange}$. As $n^{\prime}$ is bounded by
$O(\sigma^{O(1)})$, each element of the index array $I(u)$ of each node $u$
can be encoded with $O(\lg\sigma)=O(\sqrt{\lg n})$ bits. We then build the
predecessor/successor data structure over $I(u)$ using Lemma B.4. Given that
$\mathtt{point}$ takes $O(\lg(\lg\sigma/\lg d))$ time, $\mathtt{noderange}$
can be answered in $O(\lg\lg\sigma+\lg(\lg\sigma/\lg d))=O(\lg\lg\sigma)$ time
without explicitly storing $I(u)$. By Lemma B.4, this data structure occupies
$O(|I(u)|\lg\lg\sigma)$ extra bits of space and can be built upon $I(u)$ in
$O(|I(u)|/\sqrt{\lg n}+1)$ time. As $T$ has $\sigma$ nodes and $h+1$ levels,
the overall time needed to construct it over all nodes is
$\sum_{u}O(|I(u)|/\sqrt{\lg n}+1)=O(n^{\prime}\lg\sigma/(\sqrt{\lg n}\times\lg
d)+\sigma)$ bounded by $O(n^{\prime}{\lg^{2}\sigma}/{\lg
n}+\sigma\log_{d}\sigma)$. Similarly, the overall extra space cost is
$O(n^{\prime}\lg\lg\sigma\log_{d}\sigma)$ bits. Therefore, the overall space
cost required by the data structure designed is
$O(n^{\prime}\lg\sigma\lg(\lg\sigma/\lg
d)+n^{\prime}\lg\lg\sigma\log_{d}\sigma+\sigma
w)=O(n^{\prime}\lg\sigma\lg(\lg\sigma/\lg d)+\sigma w)$ bits.

###  D.3 Proof of Lemma 4.3

One may attempt to achieve this by setting $\tau$ to
$(\log_{d}\sigma)^{\epsilon}$ in Lemma D.1 to achieve constant-time support
for $\mathtt{point}$, but then the construction time is
$O(n^{\prime}\tau\lg^{2}\sigma/\lg n+\sigma\log_{d}\sigma)$, in which the
first term is not small enough. This term shows the time spent on building the
auxiliary data structures for $\mathtt{rank^{\prime}}$. To remove the $\tau$
factor in it, we have designed in Section 4 a variant of the solution by Chan
et al. [11] by storing point coordinates at a subset of levels of $T$ instead
of only at the leaf level. This twist allows us to build
$\mathtt{rank^{\prime}}$ structures at fewer tree levels to decrease the
construction time, and we still achieve the query time and space bounds that
match those in part (c) of Lemma 2.6.

######  Lemma D.5.

The data structure in Lemma 4.3 occupy
$O(n^{\prime}\lg\sigma\log_{d}^{\epsilon}\sigma+\sigma w)$ bits.

######  Proof D.6.

We only discuss the space usage of all $\mathit{S\\!p}(u)$’s and the space
cost of $\mathtt{rank^{\prime}}$ data structure built over
$\mathit{S\\!p}(u)$, as the space costs of all other data structures are the
same to those in Lemma D.1. Each point in $N$ appears in the ordered point
list associated with a node $u$ at each level, $l$, of $T$. When the color,
$c$, of $l$ is not $1/\epsilon-1$, a skipping pointer is created for this
node, which encodes the rank of the descendant of $u$ among all the
descendants of $u$ at level $l^{\prime}=\tau^{c+1}\lceil l/\tau^{c+1}\rceil$.
As $u$ has $d^{l^{\prime}-l}\leq d^{\tau^{c+1}}$ descendants at level
$l^{\prime}$, $\mathit{S\\!p}(v)[j]$ can be encoded using at most
$\tau^{c+1}\lg d$ bits. Since there are at most $\log_{d}\sigma/\tau^{c}$
levels with color $c$, the skipping pointers created for this point across all
levels of $T$ occupy at most
$\sum_{c=0}^{1/\epsilon-2}\frac{\log_{d}\sigma}{\tau^{c}}\times\tau^{c+1}\times\lg
d=O(\tau\lg\sigma)$ bits. As there are $n^{\prime}$ points in $N$, the space
usage of all skipping pointers is
$O(n^{\prime}\lg\sigma\log_{d}^{\epsilon}\sigma)$ bits. By Lemma 3.5, the
extra space cost needed to build data structures to support
$\mathtt{rank^{\prime}}$ in sequences of skip pointers is also
$O(n^{\prime}\lg\sigma\log_{d}^{\epsilon}\sigma)$ bits. In addition to the
other data structures shown in Lemma D.1, the overall space cost is
$O(n^{\prime}\lg\sigma\log_{d}^{\epsilon}\sigma+\sigma w)$ bits.

######  Lemma D.7.

The new data structures can support $\mathtt{point}(v,i)$ in $O(1)$ time.

######  Proof D.8.

We retrieve the depth, $l$, of $v$ to get the color, $c$, assigned to level
$l$. If $c=1/\epsilon-1$, then $N(v)$ is stored explicitly, and we return
$N(v)[i]$ as the answer. Otherwise, let $l^{\prime}=\tau^{c+1}\lceil
l/\tau^{c+1}\rceil$. Then the point $p$ that we will eventually return as the
answer to the query is also distributed to the ordered point list associated
with the $\mathit{S\\!p}(v)[i]$-th descendant, $u$, of $v$ at level
$l^{\prime}$. Node $u$ can be located in constant time using the implicit
representation of $T$ as a complete $d$-ary tree. Furthermore, $p$ is at
position $j=\mathtt{rank^{\prime}}(\mathit{S\\!p}(v),i)$ of $N(u)$. We then
perform the query $\mathtt{point}(u,j)$ recursively to compute the answer. To
bound the running time, observe that this process is terminated once we reach
a level with color $1/\epsilon-1$, and one out of every $\tau^{1/\epsilon-1}$
levels of $T$ is assigned this color. Hence, the process is applied
recursively $O(\log_{\tau}\tau^{1/\epsilon-1})=O(1)$ times, each with a cost
of $O(1)$. Therefore, it requires constant time to support
$\mathtt{point}(v,i)$.

######  Lemma D.9.

The new data structures can be constructed in
$O(n^{\prime}{\lg^{2}\sigma}/{\lg n}+\sigma\log_{d}\sigma)$ time.

######  Proof D.10.

We build $T$ and the skipping pointer sequences for its nodes as in the proof
of Lemma D.1, which uses $O(n^{\prime}{\lg^{2}\sigma}/\lg n+\sigma)$ time. We
then apply Lemma 3.5 to build the data structure for $\mathtt{rank^{\prime}}$
queries upon $\mathit{S\\!p}(u)$. As $\mathit{S\\!p}(u)$ is drawn from
alphabet $d^{l^{\prime}-l}$, this requires
$O(|\mathit{S\\!p}(u)|(l^{\prime}-l)^{2}\lg^{2}d/\lg n+d^{l^{\prime}-l})$
time, which is bounded by $O(|\mathit{S\\!p}(u)|\tau^{2c+2}\lg^{2}d/\lg
n+d^{l^{\prime}-l})$ as $l^{\prime}-l\leq\tau^{c+1}$. Hence the total time
required to build auxiliary data structures for $\mathtt{rank^{\prime}}$ for
nodes at a level with color $c$ is $O(n^{\prime}\tau^{2c+2}\lg^{2}d/\lg
n+\sigma)$. As there are at most $\log_{d}\sigma/\tau^{c}$ levels with color
$c$, the total construction time over all levels of $T$ is
$\sum_{c=0}^{1/\epsilon-2}(\log_{d}\sigma/\tau^{c})\times
O(n^{\prime}\tau^{2c+2}\lg^{2}d/\lg n+\sigma)=O(n^{\prime}{\lg^{2}\sigma}/{\lg
n}+\sigma\log_{d}\sigma)$, which dominates the construction time of all data
structures.

##  Appendix E Proofs Omitted From Section 5

###  E.1 Using Range Maximum/Minimum to Answer 3-Sided Queries in the Proof of
Lemma 5.1

To report points in $([a,+\infty)\times[c_{l},d_{l}])\cap N(u_{l})$, we need
only report the points in $N(u_{l})[c_{l},d_{l}]$ whose $x$-coordinates are at
least $a$. This can be done by performing range maximum queries over
$A(u_{l})$ recursively as follows. We perform $\mathtt{rMq}(c_{l},d_{l})$ to
get the index $m$ of the point $p$ that has the maximum $x$-coordinate in
$N(u_{l})[c_{l},d_{l}]$, and retrieve its coordinates $(p.x,p.y)$ by
$\mathtt{point}(u_{l},m)$. If $p.x\geq a$, we report $p$ and perform the same
process recursively in $N(u_{l})[c_{l},m-1]$ and $N(u_{l})[m+1,d_{l}]$.
Otherwise we stop. The points in $([0,b]\times[c_{r},d_{r}])\cap N(u_{r})]$
can be reported in a similar way. To analyze the query time, observe that we
perform $\mathtt{noderange}$ twice in $O(\lg\lg n)$ time. The recursive
procedure is called $O(\mathtt{occ})$ times, and each time it is performed, it
uses $O(1)$ time. All other steps require $O(1)$ time. Therefore, the overall
query time is $O(\lg\lg n+\mathtt{occ})$.

###  E.2 The Analysis of the Space Usage and Construction Time for Data
Structure in Lemma 5.3

Our analysis requires previous result shown as follows:

######  Lemma E.1 ([11, Section 2],[7, Lemma 5]).

Given a set, $N$, of $n$ points in $[u]\times[u]$, a data structure of
$O(n\lg^{1+\epsilon}n)$ bits can be constructed in $O(n\lg n)$ time, which
supports orthogonal range reporting over $N$ in $O(\lg\lg u+\mathtt{occ})$
time, where $\mathtt{occ}$ is the number of reported points.

With this lemma, we now give the analysis of the space usage and construction
time for the data structure in Lemma 5.3.

######  Lemma E.2.

The data structure in Lemma 5.3 occupies
$O(n^{\prime}\lg^{1/2+\epsilon}n+w(2^{\sqrt{\lg n}}+n^{\prime}/2^{\sqrt{\lg
n}}))$ bits of space and can be constructed in $O(n^{\prime}+\sqrt{\lg n}\cdot
2^{\sqrt{\lg n}})$ time.

######  Proof E.3.

To bound the storage costs, by Lemma 5.1, the orthogonal range reporting
structure over each $N_{i}$ uses $O(2^{2\sqrt{\lg
n}}\lg^{1/2+\epsilon}n+w2^{\sqrt{\lg n}})$ bits. Thus, the range reporting
structures over $N_{0},N_{1},\ldots,N_{n/b-1}$ occupy
$O((n^{\prime}/b)\times(2^{2\sqrt{\lg n}}\lg^{1/2+\epsilon}n+w\cdot
2^{\sqrt{\lg n}}))=O(n^{\prime}\lg^{1/2+\epsilon}n+n^{\prime}w/2^{\sqrt{\lg
n}})$. As there are at most $n^{\prime}/2^{\sqrt{\lg n}}$ points in $\hat{N}$,
by Lemma E.1, the range reporting structure for $\hat{N}$ occupies
$O(n^{\prime}\lg^{1+\epsilon}n/2^{\sqrt{\lg n}})=o(n^{\prime})$ bits. There
are $n^{\prime}$ points in all $P_{i,j}$’s and each of their local
$y$-coordinates can be encoded in $\lg b=2\sqrt{\lg n}$ bits. In addition,
each $P_{i,j}$ requires a pointer to encode its memory location, so
$n^{\prime}/b\times 2^{\sqrt{\lg n}}=n^{\prime}/2^{\sqrt{\lg n}}$ pointers are
needed. Therefore, the total storage cost of all $P_{i,j}$’s is
$O(n^{\prime}w/2^{\sqrt{\lg n}}+n^{\prime}\sqrt{\lg n})$. Thus the space costs
of all structures add up to
$O(n^{\prime}\lg^{1/2+\epsilon}n+n^{\prime}w/2^{\sqrt{\lg n}})$ bits. Note
that the above analysis assumes $n^{\prime}>b$. Otherwise,
$O(n^{\prime}\lg^{1/2+\epsilon}n+w\cdot 2^{\sqrt{\lg n}})$ bits are needed, so
we use $O(n^{\prime}\lg^{1/2+\epsilon}n+w\cdot 2^{\sqrt{\lg
n}}+n^{\prime}w/2^{\sqrt{\lg n}})$ as the space bound on both cases.

Regarding construction time, when $n^{\prime}>b$, observe that the point sets
$N_{0},N_{1},\ldots,N_{n^{\prime}/b-1}$ and $\hat{N}$, as well as the
sequences $P[i,j]$ for $i=0,1,\ldots,n^{\prime}/b-1$ and
$j=0,1,\ldots,2^{\sqrt{\lg n}}-1$, can be computed in $O(n^{\prime})$ time. By
Lemma E.1, The range reporting structure for $\hat{N}$ can be built in
$O(n^{\prime}/b\times\lg n)=o(n^{\prime})$ time. Finally, the total
construction time of the range reporting structures for
$N_{0},N_{1},\ldots,N_{n/b-1}$ is $O({n^{\prime}}/{2^{2\sqrt{\lg
n}}}\times(2^{2\sqrt{\lg n}}+\sqrt{\lg n}\times 2^{\sqrt{\lg
n}}))=O(n^{\prime})$, which dominates the total preprocessing time of all our
data structures. When $n^{\prime}\leq b$, the construction time is
$O(n^{\prime}+\sqrt{\lg n}\cdot 2^{\sqrt{\lg n}})$ by Lemma 5.1, so we use
$O(n^{\prime}+\sqrt{\lg n}\cdot 2^{\sqrt{\lg n}})$ as the upper bound on
construction time in both cases.

###  E.3 The Analysis of Space Usage and Construction Time for Data Structure
in Lemma 5.5

######  Lemma E.4.

The data structure in Lemma 5.5 occupies $O(n\lg^{1+\epsilon}\sigma+n\lg n)$
bits of space for any constant $\epsilon>0$ and can be constructed in
$O(n{\lg\sigma}/{\sqrt{\lg n}})$ time.

######  Proof E.5.

Now we analyze the space costs. $T$ with support for ball inheritance uses
$O(n\lg^{1+\epsilon}\sigma+n\lg n)$ bits for any positive $\epsilon$. For each
internal node $v$, since $w=\Theta(\lg n)$, the data structure for range
reporting over $\hat{S}$ uses
$O(|S(u)|\lg^{1/2+\epsilon^{\prime}}n+2^{\sqrt{\lg n}}\lg n+|S(u)|\lg
n/2^{\sqrt{\lg n}})$ bits for any positive $\epsilon^{\prime}$. This subsumes
the cost of storing $M(u)$ which is $O(|A(u)|)$ bits. As $T$ has
$O(\sigma/2^{\sqrt{\lg n}})$ internal nodes, the total cost of storing these
structures at all internal nodes is
$\sum_{u}O(|S(u)|\lg^{1/2+\epsilon^{\prime}}n+2^{\sqrt{\lg n}}\lg n+|S(u)|\lg
n/2^{\sqrt{\lg n}})=O(n\lg\sigma/\sqrt{\lg
n}\times\lg^{1/2+\epsilon^{\prime}}n+\sigma\lg
n)=O(n\lg\sigma\lg^{\epsilon^{\prime}}n+\sigma\lg n)$. As $\lg
n\leq\lg^{2}\sigma$ and $\sigma\leq n$, this is bounded by
$O(n\lg^{1+2\epsilon^{\prime}}\sigma)$. Setting
$\epsilon^{\prime}=\epsilon/2$, the space bound turns to be
$O(n\lg^{1+\epsilon}\sigma)$ bits. Overall, the data structures occupy
$O(n\lg^{1+\epsilon}\sigma+n\lg n)$ bits.

Finally, we analyze the construction time. As shown in Lemma 4.1, $T$ with
support for ball inheritance can be constructed in $O(n\lg\sigma/\sqrt{\lg
n})$ time. For each internal node $u$ of $T$, constructing $M(u)$ and the
range reporting structure over $\hat{S}(v)$ requires
$O(|A(u)|+|S(u)|+\sqrt{\lg n}\cdot 2^{\sqrt{\lg n}})=O(|S(u)|+\sqrt{\lg
n}\cdot 2^{\sqrt{\lg n}})$ time. As $T$ has $O(\sigma/2^{\sqrt{\lg n}})$
internal nodes, these structures over all internal nodes can be built in
$\sum_{u}O(|S(u)|+\sqrt{\lg n}\times 2^{\sqrt{\lg n}})=O(n\lg\sigma/\sqrt{\lg
n}+\sigma\sqrt{\lg n})=O(n\lg\sigma/\sqrt{\lg n})$ as $\sigma\leq n$. The
preprocessing time of all data structures is hence $O(n\lg\sigma/\sqrt{\lg
n})$.

##  Appendix F Optimal Orthogonal Range Successor with Fast Preprocessing

We now design data structures over $n$ points in 2d rank space that support an
orthogonal range successor query in optimal time and can be constructed fast.