Optimal Encodings for Range Majority Queries

摘要

We study the problem of designing a data structure that reports the positions of the distinct iota-majorities within any range of an array A[1, n], without storing A. A iota-majority in a range A[i, j], for 0 < iota < 1, is an element that occurs more than iota(j - i + 1) times in A[i, j]. We show that Omega (n inverter right perpendicular log(1/iota) inverter left perpendicular) bits are necessary for any data structure just able to count the number of distinct iota-majorities in any range. Then, we design a structure using O (n inverter right perpendicular log(1/iota) inverter left perpendicular) bits that returns one position of each iota-majority of A[i, j] in O((1/iota) log log(w) (1/iota) log n) time, on a RAM machine with word size w (it can output any further position where each iota-majority occurs in Omicron(1) additional time). Finally, we show how to remove a log n factor from the time by adding Omicron(n log log n) bits of space to the structure.