Range majority in constant time and linear space

Given an array $A$ of size $n$, we consider the problem of answering range majority queries: given a query range $[ildots j]$ where $1le ile jle n$, return the majority element of the subarray $A[ildots j]$ if it exists. We describe a linear space data structure that answers range majority queries in constant time. We further generalize this problem by defining range $-majority queries: given a query range $[ildots j]$, return all the elements in the subarray $A[ildots j]$ with frequency greater than $alpha (j−i+1)$. We prove an upper bound on the number of $-majorities that can exist in a subarray, assuming that query ranges are restricted to be larger than a given threshold. Using this upper bound, we generalize our range majority data structure to answer range $-majority queries in $O(1alpha)$ time using $O(n lg (1alpha+1))$ space, for any fixed $alphain (0,1)$. This result is interesting since other similar range query problems based on frequency have nearly logarithmic lower bounds on query time when restricted to linear space.