Encodings for Range Majority Queries

Gonzalo Navarro and Sharma V. Thankachan

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 tau-majorities.