Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries

We study the fundamental question of how efficiently suffix array entries can be accessed when the array cannot be stored explicitly. The suffix array \(\mathrm{SA}_T[1..n]\) of a text \(T\) of length \(n\) encodes the lexicographic order of its suffixes and underlies numerous applications in pattern matching, data compression, and bioinformatics. Previous work established one-way reductions showing how suffix array queries can be answered using, for example, rank queries on the Burrows—Wheeler Transform. More recently, a new class of prefix queries was introduced, together with reductions that, among others, transform a simple tradeoff for prefix-select queries into a suffix array tradeoff matching state-of-the-art space and query-time bounds, while achieving sublinear construction time. For binary texts, the resulting data structure achieves space \(\mathcal{O}(n)\) bits, preprocessing time \(\mathcal{O}(n/\sqrt{\log n})\), preprocessing space \(\mathcal{O}(n)\) bits, and query time \(\mathcal{O}(\log^\epsilon n)\) for any constant \(\epsilon \gt 0\). However, whether these bounds could be improved using different techniques has remained open.