Compressed Dynamic Range Majority Data Structures
Travis Gagie, Meng He, Gonzalo Navarro · 2017
In the range α-majority query problem, we preprocess a given sequence S[1..n] for a fixed threshold α ∈ (0, 1], such that given a query range [i..j], the symbols that occur more than α (j-i+1) times in S[i..j] can be reported efficiently. We design the first compressed solution to this problem in dynamic settings. Our data structure represents S using nHko(nlg σ) bits for any k = o(log σ n), where σ is the alphabet size and Hkis the k-th order empirical entropy of S. It answers range α-majority queries in O((lg n)/(α lg lgn)) time, and supports insertions and deletions in O(lg n/α) amortized time. The best previous solution [1] has the same query and update times, but uses O(n) words.