Abstract

We face the problem of designing a data structure that can report the majority within any range of an array A[1, n], without storing A. We show that Omega(n) bits are necessary for such a data structure, and design a structure using O(n log* n) bits that answers majority queries in O(log n) time. We extend our results to T-majorities.