Summary: We propose a space-efficient data structure for orthogonal range search on suffix arrays. For general two-dimensional orthogonal range search problem on a set of \(n\) points, there exists an \(n\log n(1+o(1))\)-bit data structure supporting \(O(\log n)\)-time counting queries [V. Mäkinen and G. Navarro, Theor. Comput. Sci. 387, No. 3, 332–347 (2007; Zbl 1144.68023)]. The space matches the information-theoretic lower bound. However, if we focus on a point set representing a suffix array, there is a chance to obtain a space efficient data structure. We answer this question affirmatively. Namely, we propose a data structure for orthogonal range search on suffix arrays which uses \(O(\frac{1}{\varepsilon}n(H_0+1))\) bits where \(H_0\) is the order-\(0\) entropy of the string and answers a counting query in \(O(n^\varepsilon)\) time for any constant \(\varepsilon>0\). As an application, we give an \(O(\frac{1}{\varepsilon}n(H_0+1))\)-bit data structure for the range LCP problem.
For the entire collection see [Zbl 1436.68029].