Dynamic Range Majority Data Structures

Amr Elmasry, Meng He, J. Ian Munro +1

Given a set $P$ of coloured points on the real line, we study the problem of answering range $\alpha$-majority (or "heavy hitter") queries on $P$. More specifically, for a query range $…