Optimal Query Time for Encoding Range Majority

Pawel Gawrychowski, Patrick K. Nicholson

We revisit the range $\tau$-majority problem, which asks us to preprocess an array $A[\mathrm{1..}n]$ for a fixed value of $\tau \in (0,1/2]$, such that for any query range $[i,j]$ we can return a…