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.