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.