2016/11/06 by Gagie, Travis, He, Meng, Navarro, Gonzalo
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1611.01835
In the range α-majority query problem, we are given a sequence S[1..n] and a fixed threshold α∈ (0, 1), and are asked to preprocess S such that, given a query range [i..j], we can efficiently report the symbols that occur more than α(j-i+1) times in S[i..j], which are called the range α-majorities. In this article we first describe a dynamic data structure that represents S in compressed space --- nHk+ o(n\lg σ) bits for any k = o(logσ n), where σ is the alphabet size and Hk ≤ H0 ≤ \lgσ is the k-th order empirical entropy of S --- and answers queries in O ((log n)/(αlog log n) ) time while supporting insertions and deletions in S in O ( \frac\lg nα ) amortized time. We then show how to modify our data structure to receive some β≥ α at query time and report the range β-majorities in O ( (log n)/(βlog log n) ) time, without increasing the asymptotic space or update-time bounds. The best previous dynamic solution has the same query and update times as ours, but it occupies O(n) words and cannot take advantage of being given a larger threshold β at query time. [ABSTRACT CLIPPED DUE TO LENGTH.]