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

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+\occ)$ time, where $\occ$ 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+\occ)$ time. The query times of these data structures are optimal when the space costs must be within $O(n\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. We also apply our results to improve the construction time of text indexes.