Optimal Encodings for Range Majority Queries

Abstract

We study the problem of designing a data structure that reports the positions of the distinct τ -majorities within any range of an array A[1, n], without storing A. A τ -majority in a range A[i, j ], for 0 < τ < 1, is an element that occurs more than τ( j − i + 1) times in A[i, j ]. We show that (n log(1/τ ) ) bits are necessary for any data structure just able to count the number of distinct τ -majorities in any range. Then, we design a structure using O(n log(1/τ ) ) bits that returns one position of each τ -majority of A[i, j ] in O((1/τ ) log logw(1/τ ) log n) time, on a RAM machine with word size w (it can output any further position where each τ -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.