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 [i..j][i..j] where 1⩽i⩽j⩽n1⩽i⩽j⩽n, return the majority element of the subarray A[i..j]A[i..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 [i..j][i..j], return all the elements in the subarray A[i..j]A[i..j] with frequency greater than α(j−i+1)α(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(1α) time using O(nlg(1α+1)) space, for any fixed α∈(0,1)α∈(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.