Optimal Query Time for Encoding Range Majority

We revisit the range $τ$-majority problem, which asks us to preprocess an array $A[1..n]$ for a fixed value of $τ\in (0,1/2]$, such that for any query range $[i,j]$ we can return a position in $A$ of each distinct $τ$-majority element. A $τ$-majority element is one that has relative frequency at least $τ$ in the range $[i,j]$: i.e., frequency at least $τ(j-i+1)$. Belazzougui et al. [WADS 2013] presented a data structure that can answer such queries in $O(1/τ)$ time, which is optimal, but the space can be as much as $Θ(n \lg n)$ bits. Recently, Navarro and Thankachan [Algorithmica 2016] showed that this problem could be solved using an $O(n \lg (1/τ))$ bit encoding, which is optimal in terms of space, but has suboptimal query time. In this paper, we close this gap and present a data structure that occupies $O(n \lg (1/τ))$ bits of space, and has $O(1/τ)$ query time. We also show that this space bound is optimal, even for the much weaker query in which we must decide whether the query range contains at least one $τ$-majority element.