Python O(logn) with explanation
Intuition\nLet\'s imagine that we\'re solving a simpler problem. Write a class that gets initialized with an array num and then calls verify_num_threshold(left:
## Intuition\nLet\'s imagine that we\'re solving a simpler problem. Write a class that gets initialized with an array `num` and then calls `verify_num_threshold(left: int, right: int, num: int, threshold: int)`. \n#### PART 1: Verify Candidate [O(logn)]\nOur function should return `true` if `num` occurs `>= threshold` times in `nums[left..right]`. We could answer that query in `O(logn)` time by mapping every occurance of `num` in `nums` to an array of all it\'s `indices`.\nEx:\n```\nnums = [7, 4, 3, 3, 4, 4]\nnums_idx = { 7: [0], 4: [1, 4, 5], 3: [2, 3] }\n```\nNow, we can answer query by binary searching for `left` and `right` in `nums_idx[num]` and finding `l` and `r` such that `nums_idx[num][l] == left` and `nums_idx[num][r] == right`. We will return true if `r - l >= threshold`. This is effectively an LC medium problem.\n\nBut now we have to generate  candidates in `nums` to verify. Let\'s consider our options.\n### Part 2: Generate candidates\n##### Option A: Sample numbers randomly from `nums[left..right]` [O(1)]\nIf we know that `threshold` is at minimum a strict majority of `nums[left..right]`, then each random `nums[i]` will have a `> 50%` chance of being our candidate. If we sample randomly `20` times, our chance of "missing" our candidate would be `< 0.00009536743%`. Those are pretty good odds. But let\'s consider other options.\n##### Option B: Pick most common numbers in `nums` [O(n)]\nWe could count the occurances of each element of `nums` and then iterate through those candidates in sorted order from highest to lowest. Because we eventually try every candidate in `nums`, we\'re guaranateed to eventually find the correct answer. But also because we try every candidate in `nums`, our runtime complexity is very poor at `O(n)`.\n##### Option C: Bitwise Prefix Sum [O(1)]\n**Intuition**\nThe problem specifies that `threshold` is always at minimum a *strict majority* of `right-left+1`. That means, we can only ever have one candidate that crosses `threshold`. In cases where you only need to retrieve one candidate `int` in an array of `ints`, bit hacking should be considered as an approach.\nSee: [136. Single Number](https://leetcode.com/problems/single-number/) ; [137. Single Number II](https://leetcode.com/problems/single-number-ii/) ; [260. Single Number III](https://leetcode.com/problems/single-number-iii/)\nIn `__init__`, we can precompute a bitwise prefix sum. `bit_sum[i][b]` is the sum of the b-th bit for all nums in range `[0..i)`. Our index `i` is offset by 1 so that we can query the edge case `bit_sum[0]` representing the start of the array.\nIn `query`, we reconstruct our candidate number\nAs long as `threshold` is a strict majority of `right-left+1`, we can be guaranteed that we only have 1 number that meets `threshold`. But it\'s also possible that no number meets `threshold`. In that case, we should return `-1`. Let\'s consider these 2 cases:\n##### There exists some num in nums[left..right] where count(num) >= threshold\nIn this case, each set bit (`1`) in `num` will occur *at least* `threshold` times in `nums[left..right]` and no unset bit (`0`) in `num` will occur `threshold` times because only one number can cross `threshold`.\nLikewise, each `0` bit will be `1` *less than* `threshold` times in `nums[left..right]`.\nTherefor, we can reconstruct the majority number in `nums[left..right]` simply by adding every bit in our prefix sum `bit_sum[right+1] - bit_sum[left]` where the number of `1`s crosses our threshold.\n##### There does not exist some num where count(num) >= threshold\nIf no num occurs a *majority* of times in `nums[left..right]`, then our reconstructed candidate `num` will simply be a random assortment of bits that happened to occur `>= threshold` times. So this is a problem, right? Not really. We already have our verification step constructed from Step 1. We can simply re-use that to validate whether `num` (effectively a random int) occurs `>= threshold` times and the answer will be no, so we\'ll return `-1`.\n\nIn this case, we\'ve only attempted to verify 1 candidate and that verification takes `O(logn)`. We also generated our candidate in `O(1)` time, so our total runtime complexity is `O(logn)` and our total space complexity is `O(n)` for storing both the `nums_idx` dict and the `bit_sum` prefix sum array.\n\n#### Code\nNow let\'s put part1 and part2 together in code.\n```\nMAX_N = 2*10**4\nMAX_BIT = MAX_N.bit_length()\nclass MajorityChecker:\n\n    def __init__(self, nums: List[int]):\n        n = len(nums)\n        self.bit_sum = [[0] * MAX_BIT for _ in range(n+1)]\n        for i in range(1, n+1):\n            for b in range(MAX_BIT):\n                self.bit_sum[i][b] = self.bit_sum[i-1][b] + ((nums[i-1] >> b) & 1)\n        self.num_idx = defaultdict(list)\n        for i in range(n):\n            self.num_idx[nums[i]].append(i)\n\n    def query(self, left: int, right: int, threshold: int) -> int:\n        num = 0\n        for b in range(MAX_BIT):\n            if self.bit_sum[right+1][b] - self.bit_sum[left][b] >= threshold:\n                num |= 1 << b\n        l = bisect.bisect_left(self.num_idx[num], left)\n        r = bisect.bisect_right(self.num_idx[num], right)\n        if r-l >= threshold:\n            return num\n        return -1\n```
['Bit Manipulation', 'Binary Tree', 'Prefix Sum', 'Python', 'Python3']