  Karpinski and Nekrich (2008) introduced the problem of parameterized range
majority, which asks us 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
fixed at preprocessing time, we need either $O(n \log (1 / \tau))$ space and
optimal $O(1 / \tau)$ query time or linear space and $O((1 / \tau) \log \log
\sigma)$ query time, where $\sigma$ is the alphabet size. In this paper we give
the first linear-space solution with optimal $O(1 / \tau)$ query time, even
with variable $\tau$ (i.e., specified with the query). For the case when
$\sigma$ is polynomial on the computer word size, our space is optimally
compressed according to the symbol frequencies in the string. Otherwise, either
the compressed space is increased by an arbitrarily small constant factor or
the time rises to any function in $(1/\tau)\cdot\omega(1)$. We obtain the same
results on the complementary problem of parameterized range minority introduced
by Chan et al. (2015), who had achieved linear space and $O(1 / \tau)$ query
time with variable $\tau$.

Data Structures and Algorithms