C++/Python prefix sum + bit mask solution with explanation
log 20000 <= 15, we can use 15 bits to indicate each number.\nwe can count how many 1 appear in each bit from first number to each number using prefix sum.\nand
log 20000 <= 15, we can use 15 bits to indicate each number.\nwe can count how many 1 appear in each bit from first number to each number using prefix sum.\nand construct the major number using frequency of 1 in each bit, \nif frequency of 1 >= threshold, it means this bit is 1.\nelse if frequency of 0 >= threshold, it means this bit is 0.\nelse there is no major number.\n\nif we determine the major number, check frequecny of this major number in [left, right] >= threshold,\nso uas a hash map mapping to a list to record which position number appear.\nAnd use binary search to check this major number in [left, right] >= threshold in list.\n\ntc of query is O((log20000 + logn)), sc is O(n).\n### python\n```python\nclass MajorityChecker:\n    def __init__(self, arr: List[int]):\n\t\n\t\t# record each number\'s position\n        self.occur = defaultdict(list)\n\t\t\n\t\t# each bit\'s 1 frequency\n        self.prefix = [[0] * 15]\n\t\t\n        for i, n in enumerate(arr):\n\t\t\t# append to hash map\n            self.occur[n].append(i)\n\t\t\t\n            cur = self.prefix[-1][:]\n\t\t\t# calculate prefix sum\n            for i in range(15):\n                cur[i] += n >> i & 1\n            self.prefix.append(cur)\n\n    def query(self, left: int, right: int, threshold: int) -> int:\n        candidate = 0\n        for i, (n1, n2) in enumerate(zip(self.prefix[left], self.prefix[right+1])):\n            diff = n2 - n1\n            if diff >= threshold: candidate |= 1 << i # 1 bit appear in major number\n            elif right - left + 1 - diff < threshold: return -1 # 0 and 1 are not majority, reuturn -1\n\t\t\t\n        if candidate not in self.occur: return -1\n\t\t# check frequecny of this major number in [left, right] >= threshold \n        leftmost = bisect_left(self.occur[candidate], left)\n        rightmost = bisect_right(self.occur[candidate], right)\n        return candidate if rightmost - leftmost >= threshold else -1\n```\n\n### c++\n```cpp\nclass MajorityChecker {\npublic:\n    unordered_map<int, vector<int>> occur;\n    vector<array<int, 15>> prefix;\n    \n    MajorityChecker(vector<int>& arr): prefix(1, {0}){\n        for (int i = 0; i < arr.size(); i+=1) {\n            this -> occur[arr[i]].emplace_back(i);\n            \n            auto cur = prefix.back();\n            for (int j = 0; j < 15; j+=1)\n                cur[j] += arr[i] >> j & 1;\n            this -> prefix.emplace_back(cur);\n        }\n    }\n    \n    int query(int left, int right, int threshold) {\n        auto& pre_l = this -> prefix[left], &pre_r = prefix[right+1];\n        int candidate = 0;\n        for (int i = 0, diff; i < 15; i+=1) {\n            diff = pre_r[i] - pre_l[i];\n            if (diff >= threshold) candidate |= 1 << i;\n            else if (right - left + 1 - diff < threshold) return -1;\n        }\n        \n        if (this -> occur.count(candidate) == 0) return -1;\n        int leftmost = lower_bound(occur[candidate].begin(), occur[candidate].end(), left) - occur[candidate].begin();\n        int rightmost = upper_bound(occur[candidate].begin(), occur[candidate].end(), right) - occur[candidate].begin();\n        return rightmost - leftmost >= threshold ? candidate: -1;\n    }\n};\n```
['C', 'Prefix Sum', 'Bitmask', 'Python']