###
Better Space Bounds for Parameterized Range Majority and Minority

####
Djamal Belazzougui, Travis Gagie, and Gonzalo Navarro

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
*t*.
Subsequent authors have reduced their time and space bounds such that, when
*t* is given at preprocessing time, we need either *O(n log(1/t))*
space and optimal *O(1/t)* query time or linear space and *O((1/t)
log log s)* query time, where *s* is the alphabet size. In
this paper we give the first linear-space solution with optimal *O(1/t)*
query time. For the case when *t* is given at query time, we
significantly improve previous bounds, achieving either *O(n log log s)*
space and optimal *O(1/t)* query time or compressed space and
*O((1/t) log (log(1/t)/log log n))* 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 *O(1/t)* query time even for variable *t*. 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.