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.