Segment Tree (Python)
\nimport numpy as np\n\nclass MajorityChecker:\n\n    def __init__(self, arr: List[int]):\n        self.n = len(arr)\n        self.a = arr\n        self.tree = 
```\nimport numpy as np\n\nclass MajorityChecker:\n\n    def __init__(self, arr: List[int]):\n        self.n = len(arr)\n        self.a = arr\n        self.tree = np.zeros(4 * self.n, int)\n        self.loc = collections.defaultdict(list)\n        for i, v in enumerate(arr):\n            self.loc[v].append(i)\n        self.build(1, 0, self.n - 1)\n\n    def get_num(self, val, l, r):\n        ll = bisect.bisect_left(self.loc[val], l)\n        rr = bisect.bisect_right(self.loc[val], r)\n        return rr - ll\n\n    def build(self, node, start, end):\n        if start == end:\n            self.tree[node] = self.a[start]\n        else:\n            mid = (start + end) // 2\n            l_val = self.build(node * 2, start, mid)\n            r_val = self.build(node * 2 + 1, mid + 1, end)\n            if l_val > 0 and 2 * self.get_num(l_val, start, end) > end - start + 1:\n                self.tree[node] = l_val\n            elif r_val > 0 and 2 * self.get_num(r_val, start, end) > end - start + 1:\n                self.tree[node] = r_val\n        return self.tree[node]\n\n    def query_freq(self, node, start, end, l, r):\n        if end < l or start > r:\n            return 0\n        if l <= start and end <= r:\n            if node==15:return self.tree[node]\n            return self.tree[node]\n        else:\n            mid = (start + end) // 2\n            l_val = self.query_freq(node * 2, start, mid, l, r)\n            r_val = self.query_freq(node * 2 + 1, mid + 1, end, l, r)\n            if l_val > 0 and 2 * self.get_num(l_val, l, r) > r-l + 1:\n                return l_val\n            elif r_val > 0 and 2 * self.get_num(r_val, l, r) > r-l + 1:\n                return r_val\n        return 0\n\n    def query(self, left: int, right: int, threshold: int) -> int:\n        fre_char = self.query_freq(1, 0, self.n - 1, left, right)\n        if fre_char>0 and self.get_num(fre_char, left, right) >= threshold:\n            return fre_char\n        else:\n            return -1\n```
['Tree', 'Python3']