Compressed Dynamic Range Majority and Minority Data Structures

In the range $$\alpha$$-majority query problem, we are given a sequence $$S[1\ldots n]$$ and a fixed threshold $$\alpha \in (0, 1)$$, and are asked to preprocess S such that, given a query range $$[i\ldots j]$$, we can efficiently report the symbols that occur more than $$\alpha (j-i+1)$$ times in $$S[i\ldots j]$$, which are called the range $$\alpha$$-majorities. In this article we describe the first compressed dynamic data structure for range $$\alpha$$-majority queries. It represents S in compressed space—$$nH_k+ o(n\lg \sigma )$$ bits for any $$k = o(\lg _{\sigma } n)$$, where $$\sigma$$ is the alphabet size and $$H_k \le H_0 \le \lg \sigma$$ is the kth order empirical entropy of S—and answers queries in $$O \left( \frac{\lg n}{\alpha \lg \lg n} \right)$$ time while supporting insertions and deletions in S in $$O \left( \frac{\lg n}{\alpha } \right)$$ amortized time. We then show how to modify our data structure to receive some $$\beta \ge \alpha$$ at query time and report the range $$\beta$$-majorities in $$O \left( \frac{\lg n}{\beta \lg \lg n} \right)$$ 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 $$\beta$$ at query time. We also design the first dynamic data structure for range $$\alpha$$-minority—i.e., find a non-$$\alpha$$-majority that occurs in a range—and obtain space and time bounds similar to those for $$\alpha$$-majorities. We extend the structure to find $$\varTheta (1/\alpha )$$$$\alpha$$-minorities at the same space and time cost. By giving up updates, we obtain static data structures with query time $$O((1 / \alpha ) \lg \lg _w \sigma )$$ for both problems, on a RAM with word size $$w = \varOmega (\lg n)$$ bits, without increasing our space bound. Static alternatives reach time $$O(1/\alpha )$$, but they compress S only to zeroth order entropy ($$H_0$$) or they only handle small values of $$\alpha$$, that is, $$\lg (1/\alpha ) = o(\lg \sigma )$$.