[Python] O(n) preprocess, O(logn) query. No segment tree and random. Just binary search.
The basic idea of handling query consists of two problems:\n1. Find a candidate.\n2. Check if it\'s the majority.\n\nLet\'s solve problem 2 first. \nWe have to 
The basic idea of handling query consists of two problems:\n1. Find a candidate.\n2. Check if it\'s the majority.\n\nLet\'s solve problem 2 first. \nWe have to know the number of candidate in arr[left]...arr[right].\nThere are two methods:\n1) Prefix sum.\n    Let pre[i] denote the number of candidate in arr[0]...arr[i],\n    then pre[right] - pre[left - 1] is the answer.\n    Time complexity: O(1).\n2) Binary search the index array.\n    Let v denote the index array of candidate in arr[0]...arr[n-1],\n    p1 denote the lower_bound index of left in v,\n    and p2 denote the upper_bound index of right in v,\n    then p2 - p1 is the answer.\n    Time complexity: O(logn).\n\nNow, Let\'s come to problem 1.\nThere are a lot of numbers in arr[left]...arr[right],\nand we can check one candidate quickly with the solution of problem 2,\nbut we can\'t afford to check each number one by one,\nso how should we do?\nThis problem reminds me of another familiar problem:\n\n    There are 1000 bottles of water, \n    of which one bottle contains poison.\n    You can test these water using rats,\n    and rats will die after drinking poison.\n    What\'s the minimum number of rats do you need to identify the bottle containing poison?\n[458. Poor Pigs](https://leetcode.com/problems/poor-pigs/) is a general version of it. Remember what we did to solve this problem? Group and test:\n\n    We label each bottle by binary string: 000, 001, 010, 011, ...\n    Then we group bottles with the first bit equaling 1, and test with a rat.\n    If the rat dies, we know the first bit of poisonous bottle is 1, otherwise it\'s 0.\n    We do so to test the second bit, the third bit and so on.\n    After 10 times of tests, as 2^10 = 1024 > 1000, we can identify the poisonous bottle.\nUsing the same idea, we can solve problem 1:\n\n    We label each number by binary string: 000, 001, 010, 011, ...\n    We group numbers with the first bit equaling 1, and check it.\n    if the group is the majority, we know the first bit of the candidate is 1, otherwise it\'s 0.\n    We do so to check the second bit, the third bit and so on.\n    After 15 times of tests, as 2^15 = 32768 > 20000, we can identify the candidate.\nLast but not least, after we get the candidate, we have to check it again, because it may not be the majority. \nFor example, we label array [1, 2, 3] as [01, 10, 11],\nand the candidate is 11, obviously it\'s not the majority.\nWhen check each group, we can use prefix sum method, which is O(1).\nBut when check the final candidate, we can only binary search the index array,\nbecause we can\'t afford to build prefix sum for each number, which is O(n^2).\n\nPreprocess time complexity: \n    `O(15*n) = O(n)`. You can also say it\'s `O(nlogn)` strictly.\nQuery time complexity:\n    `O(logn)`.\n\t\n```python\nfrom bisect import bisect, bisect_left\nclass MajorityChecker:\n\n    def __init__(self, arr: List[int]):\n        self.v = [[] for _ in range(20001)]\n        self.pre = [[0] * 15 for _ in range(20002)]\n        for i, a in enumerate(arr):\n            self.v[a].append(i)\n            for j in range(15):\n                self.pre[i][j] = self.pre[i - 1][j] + (a >> j & 1)\n\n    def query(self, left: int, right: int, threshold: int) -> int:\n        a = 0\n        for j in range(15):\n            if self.pre[right][j] - self.pre[left - 1][j] >= threshold:\n                a |= 1 << j\n        return a if bisect(self.v[a], right) - bisect_left(self.v[a], left) >= threshold else -1\n```
[]