Given N numbers and M range queries (starting and ending points), I need to compute majority (most frequent element, if it exists) in these ranges.I'm looking for an algorithm that would answer queries in logarithmic or even constant time.
Range majority queries - most freqent element in range
algorithms;search algorithms
If the $N$ items are in ascending sorted order and stored into an array, you can determine a majority candidate in $O(1)$ time for a specified range by returning the item whose index is the range median. Therefore, this will require $O(M)$ time in the worst case for $M$ range queries. Note that the item returned in each query is a candidate: you need to verify if the item actually is a majority element in the range. And, verification is linear in the number of items in the range.EDIT: explained tradeoff between space and timeIf the items are not in sorted order, than finding a candidate element requires in the worst case time linear  in the number of items in the range, using the Boyer-Moore algorithm and constant space (one counter). You can not determine a candidate element in time logarithmic in the number of items in the range while using constant space. However, if you trade space for time, you can determine a majority element in $O(1)$ time at the cost of using linear space.