[Python] Segment tree (merge in O(1), query O(log n))
\nfrom bisect import bisect, bisect_left\nclass Node():\n    def __init__(self, val, freq):\n        self.val = val\n        self.freq = freq\n        \ndef mer
```\nfrom bisect import bisect, bisect_left\nclass Node():\n    def __init__(self, val, freq):\n        self.val = val\n        self.freq = freq\n        \ndef merge(a,b):\n    if a.val == b.val:\n        return Node(a.val, a.freq+b.freq)\n    if a.freq > b.freq:\n        return Node(a.val, a.freq - b.freq)\n    return Node(b.val, b.freq - a.freq)\n\nclass MajorityChecker:\n\n    def __init__(self, arr: List[int]):\n        self.n = len(arr)\n        self.arr = arr\n        self.size = 1 << math.ceil(math.log(self.n, 2)) + 1 \n        self.tree = [None] * self.size \n        self.indexes = {i: [] for i in self.arr}\n        self.build(0, 0, self.n-1)\n           \n    def build(self, pos, l, r):\n        if l == r:\n            self.tree[pos] = Node(self.arr[l], 1) \n            self.indexes[self.arr[l]].append(l)\n        else:\n            mid = l + r >> 1\n            self.build(pos*2+1, l, mid) \n            self.build(pos*2+2,mid+1, r) \n            self.tree[pos] = merge(self.tree[pos*2+1], self.tree[pos*2+2]) \n        \n    def pquery(self, pos, start, end, l ,r):\n        if l > end or r < start:\n            return Node(0, 0)\n        if start <= l and r <= end:\n            return self.tree[pos] \n        mid = l + r >> 1\n        a = self.pquery(pos*2+1, start, end, l, mid) \n        b = self.pquery(pos*2+2, start, end, mid+1, r) \n        return merge(a,b)\n\n    def query(self, l: int, r: int, threshold: int) -> int:\n        candidate = self.pquery(0, l, r, 0 , self.n-1).val\n        if candidate == 0 : return -1\n        s = bisect_left(self.indexes[candidate], l) \n        e = bisect(self.indexes[candidate], r)\n        return candidate if e - s >= threshold else -1\n```
[]