Optimal Encodings for Range Majority Queries

Gonzalo Navarro, Sharma V. Thankachan

We study the problem of designing a data structure that reports the positions of the distinct $\tau$-majorities within any range of an array $A[1,n]$, without storing $A$. A $\tau$-major…