Younan Gao

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

2020 · arXiv (Cornell University)

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^ε n)$-word …