Better Space Bounds for Parameterized Range Majority and Minority

Karpinski and Nekrich (2008) introduced the problem of parameterized range majority, which asks to preprocess a string of length $n$ such that, given the endpoints of a range, one can quickly find all the distinct elements whose relative frequencies in that range are more than a threshold $\tau$. Subsequent authors have reduced their time and space bounds such that, when $\tau$ is given at preprocessing time, we need either $\text{Oh}n\log (1\mathrm{/}\tau )$ space and optimal $\text{Oh}1\mathrm{/}\tau$ query time or linear space and $\Oh{(1 / \tau) \log \log \sigma}$querytime,where$\sigma$ is the alphabet size. In this paper we give the first linear-space solution with optimal $\text{Oh}1\mathrm{/}\tau$ query time. For the case when $\tau$ is given at query time, we significantly improve previous bounds, achieving either $\text{Oh}n\log \log \sigma$ space and optimal $\text{Oh}1\mathrm{/}\tau$ query time or compressed space and $\Oh{(1 / \tau) \log \frac{\log (1 / \tau)}{\log w}}$ query time. Along the way, we consider the complementary problem of parameterized range minority that was recently introduced by Chan et al.\ (2012), who achieved linear space and $\Oh{1 / \tau}$querytimeevenforvariable$\tau$. We improve their solution to use either nearly optimally compressed space with no slowdown, or optimally compressed space with nearly no slowdown. Some of our intermediate results, such as density-sensitive query time for one-dimensional range counting, may be of independent interest.