1157. Online Majority Element In Subarray
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Node:\n    def __init__(self):\n        self.l = self.r = 0\n        self.x = self.cnt = 0\n\n\nclass SegmentTree:\n    def __init__(self, nums):\n        self.nums = nums\n        n = len(nums)\n        self.tr = [Node() for _ in range(n << 2)]\n        self.build(1, 1, n)\n\n    def build(self, u, l, r):\n        self.tr[u].l, self.tr[u].r = l, r\n        if l == r:\n            self.tr[u].x = self.nums[l - 1]\n            self.tr[u].cnt = 1\n            return\n        mid = (l + r) >> 1\n        self.build(u << 1, l, mid)\n        self.build(u << 1 | 1, mid + 1, r)\n        self.pushup(u)\n\n    def query(self, u, l, r):\n        if self.tr[u].l >= l and self.tr[u].r <= r:\n            return self.tr[u].x, self.tr[u].cnt\n        mid = (self.tr[u].l + self.tr[u].r) >> 1\n        if r <= mid:\n            return self.query(u << 1, l, r)\n        if l > mid:\n            return self.query(u << 1 | 1, l, r)\n        x1, cnt1 = self.query(u << 1, l, r)\n        x2, cnt2 = self.query(u << 1 | 1, l, r)\n        if x1 == x2:\n            return x1, cnt1 + cnt2\n        if cnt1 >= cnt2:\n            return x1, cnt1 - cnt2\n        else:\n            return x2, cnt2 - cnt1\n\n    def pushup(self, u):\n        if self.tr[u << 1].x == self.tr[u << 1 | 1].x:\n            self.tr[u].x = self.tr[u << 1].x\n            self.tr[u].cnt = self.tr[u << 1].cnt + self.tr[u << 1 | 1].cnt\n        elif self.tr[u << 1].cnt >= self.tr[u << 1 | 1].cnt:\n            self.tr[u].x = self.tr[u << 1].x\n            self.tr[u].cnt = self.tr[u << 1].cnt - self.tr[u << 1 | 1].cnt\n        else:\n            self.tr[u].x = self.tr[u << 1 | 1].x\n            self.tr[u].cnt = self.tr[u << 1 | 1].cnt - self.tr[u << 1].cnt\n\n\nclass MajorityChecker:\n    def __init__(self, arr: List[int]):\n        self.tree = SegmentTree(arr)\n        self.d = defaultdict(list)\n        for i, x in enumerate(arr):\n            self.d[x].append(i)\n\n    def query(self, left: int, right: int, threshold: int) -> int:\n        x, _ = self.tree.query(1, left + 1, right + 1)\n        l = bisect_left(self.d[x], left)\n        r = bisect_left(self.d[x], right + 1)\n        return x if r - l >= threshold else -1\n\n\n# Your MajorityChecker object will be instantiated and called as such:\n# obj = MajorityChecker(arr)\n# param_1 = obj.query(left,right,threshold)\n```
['Python3']