###
Optimal Encodings for Range Majority Queries

####
Gonzalo Navarro and Sharma 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*-majority in a range *A[i,j]*, for *0 < tau < 1*, is an element that
occurs more than *tau (j-i+1)* times in *A[i,j]*. We show that
*Omega(n ceil(log(1/tau)))* bits are necessary for any data structure
just able
to count the number of distinct *tau*-majorities in any range. Then, we
design a structure using *O(n ceil(log(1/tau)))* bits that returns one
position of
each *tau*-majority of *A[i,j]* in
*O((1/tau) log log_w(1/tau) log n)*
time,
on a RAM machine with word size *w* (it can output any further position where
each *tau*-majority occurs in *O(1)* additional time). Finally, we show how
to remove a *log n* factor from the time by adding *O(n log log
n)* bits of
space to the structure.