Design a data structure that efficiently finds the majority element of a given subarray.

The majority element of a subarray is an element that occurs threshold times or more in the subarray.

Implementing the MajorityChecker class:


	MajorityChecker(int[] arr) Initializes the instance of the class with the given array arr.
	int query(int left, int right, int threshold) returns the element in the subarray arr[left...right] that occurs at least threshold times, or -1 if no such element exists.


&nbsp;
Example 1:

Input
["MajorityChecker", "query", "query", "query"]
[[[1, 1, 2, 2, 1, 1]], [0, 5, 4], [0, 3, 3], [2, 3, 2]]
Output
[null, 1, -1, 2]

Explanation
MajorityChecker majorityChecker = new MajorityChecker([1, 1, 2, 2, 1, 1]);
majorityChecker.query(0, 5, 4); // return 1
majorityChecker.query(0, 3, 3); // return -1
majorityChecker.query(2, 3, 2); // return 2


&nbsp;
Constraints:


	1 &lt;= arr.length &lt;= 2 * 104
	1 &lt;= arr[i] &lt;= 2 * 104
	0 &lt;= left &lt;= right &lt; arr.length
	threshold &lt;= right - left + 1
	2 * threshold &gt; right - left + 1
	At most 104 calls will be made to query.


MAX_N = 2*10**4
MAX_BIT = MAX_N.bit_length()
class MajorityChecker:

    def __init__(self, nums: List[int]):
        n = len(nums)
        self.bit_sum = [[0] * MAX_BIT for _ in range(n+1)]
        for i in range(1, n+1):
            for b in range(MAX_BIT):
                self.bit_sum[i][b] = self.bit_sum[i-1][b] + ((nums[i-1] >> b) & 1)
        self.num_idx = defaultdict(list)
        for i in range(n):
            self.num_idx[nums[i]].append(i)

    def query(self, left: int, right: int, threshold: int) -> int:
        num = 0
        for b in range(MAX_BIT):
            if self.bit_sum[right+1][b] - self.bit_sum[left][b] >= threshold:
                num |= 1 << b
        l = bisect.bisect_left(self.num_idx[num], left)
        r = bisect.bisect_right(self.num_idx[num], right)
        if r-l >= threshold:
            return num
        return -1
class MajorityChecker {
    
    private final int digits=15;
    private int[][]presum;
    private ArrayList<Integer>[]pos;
    
    public MajorityChecker(int[] arr) {
        int len=arr.length;
        presum=new int[len+1][digits];
        pos=new ArrayList[20001];
        
        for(int i=0;i<len;i++){
            int n=arr[i];
            if(pos[n]==null)pos[n]=new ArrayList();
            pos[n].add(i);
            
            for(int j=0;j<digits;j++){
                presum[i+1][j]=presum[i][j]+(n&1);
                n>>=1;
            }
        }
    }
    
    public int query(int left, int right, int threshold) {
        int ans=0;
        for(int i=digits-1;i>=0;i--){
            int cnt=presum[right+1][i]-presum[left][i];
            int b=1;
            if(cnt>=threshold)b=1;
            else if(right-left+1-cnt>=threshold)b=0;
            else return -1;
            ans=(ans<<1)+b;
        }
        
        // check
        ArrayList<Integer>list=pos[ans];
        if(list==null)return -1;
        int L=floor(list,left-1);
        int R=floor(list,right);
        if(R-L>=threshold)return ans;
        return -1;
    }
    
    private int floor(ArrayList<Integer>list,int n){
        int left=0, right=list.size()-1, mid;
        while(left<=right){
            mid=left+(right-left)/2;
            int index=list.get(mid);
            if(index==n)return mid;
            else if(index<n)left=mid+1;
            else right=mid-1;
        }
        return right;
    }
    
}
class MajorityChecker {
public:
    MajorityChecker(vector<int>& arr) {
        this->arr = arr;
        map<int, int> cnt;
        for (auto& v: arr) {
            cnt[v]++;
        }
        val_idx = vector<int>(20001, -1);
        for (auto it = cnt.begin(); it != cnt.end(); ++it) {
            if (it->second >= 250) {
                val_idx[it->first] = elems.size();
                elems.push_back(it->first);
            }
        }
        n = elems.size();
        pre = vector<vector<int>>(n, vector<int>(arr.size(), 0));
        if (val_idx[arr[0]] != -1)
            pre[val_idx[arr[0]]][0]++;
        for (int i = 1; i < arr.size(); ++i) {
            for (int j = 0; j < n; ++j) {
                pre[j][i] = pre[j][i-1];
            }
            if (val_idx[arr[i]] != -1)
                pre[val_idx[arr[i]]][i]++;
        }
    }

    int query(int left, int right, int threshold) {
        int width = right - left + 1;
        if (width < 500) {
            map<int, int> cnt;
            int most_frequent = 0;
            int most_frequent_val;
            while (left <= right) {
                if (++cnt[arr[left++]] > most_frequent) {
                    most_frequent = cnt[arr[left - 1]];
                    most_frequent_val = arr[left - 1];
                }
                // early end condition, there are not enough elements left
                if (right + most_frequent + 1 < threshold + left) return -1;
            }
            return most_frequent >= threshold ? most_frequent_val : -1;
        }

        for (int i = 0; i < n; ++i) {
            if (pre[i][right] - (left - 1 >= 0 ? pre[i][left - 1] : 0) >= threshold) {
                return elems[i];
            }
        }
        return -1;
    }

private:
    vector<int> arr;
    vector<int> elems;
    vector<int> val_idx;
    int n;
    vector<vector<int>> pre;
};
var MajorityChecker = function(arr) {
    this.arr = arr;
};

MajorityChecker.prototype.query = function(left, right, threshold) {
    var candidate = 0
    var count = 0
    for (var i = left; i < right+1; i++) {
        if (count == 0) {
            candidate = this.arr[i];
            count = 1;
        }
        else if (candidate == this.arr[i]) {
            count += 1
        }
        else {
            count -= 1
        }
    }
    
    count = 0
    for (var i = left; i < right+1; i++) {
        if (candidate == this.arr[i]) {
            count += 1
        }
    }

    if (count >= threshold) {
        return candidate
    }   
    return -1
};
Online Majority Element In Subarray