Build a segment tree, in each node you store the element which is in majority in that node and its frequency, while merging 2 children, the element which is in majority in the whole range will be from one of the children. Now to answer queries, represent the range by the segement tree nodes which cover it, for each node check if the element which is in majority there is also in majority in the query range , each check is Log N using 2 binary searches and you check a total of log N elements per query. Thus complexity is O(N log^2 N).