Python Standard segment tree solution (Time Limit Exceeded)
\nclass Node:\n    def __init__(self, start, end, x):\n        self.start = start\n        self.end = end\n        self.counter = collections.Counter([x])\n    
```\nclass Node:\n    def __init__(self, start, end, x):\n        self.start = start\n        self.end = end\n        self.counter = collections.Counter([x])\n        self.left = None\n        self.right = None\n\ndef merge_counter(c1, c2):\n    c = collections.Counter()\n    for k in c1:\n        c[k] = c.get(k, 0) + c1[k]\n    for k in c2:\n        c[k] = c.get(k, 0) + c2[k]\n    return c\n    \nclass MajorityChecker:\n    def __init__(self, arr: List[int]):\n        def createTree(arr, l, r):\n            if l > r:\n                return None\n            if l == r:\n                return Node(l, r, arr[l])\n            root = Node(l, r, 0)\n            mid = (l + r) // 2\n            root.left = createTree(arr, l, mid)\n            root.right = createTree(arr, mid + 1, r)\n            root.counter = merge_counter(root.left.counter, root.right.counter)\n            return root\n        \n        self.root = createTree(arr, 0, len(arr) - 1)\n\n    def query(self, left: int, right: int, threshold: int) -> int:\n        def counter(root, i, j):\n            if root.start == i and root.end == j:\n                return root.counter\n            mid = (root.start + root.end) // 2\n            if j <= mid:\n                return counter(root.left, i, j)\n            elif i >= mid + 1:\n                return counter(root.right, i, j)\n            else:\n                l_counter = counter(root.left, i, mid)\n                r_counter = counter(root.right, mid + 1, j)\n                return merge_counter(l_counter, r_counter)\n        \n        count = counter(self.root, left, right)\n        x, x_freq = count.most_common(1)[0]\n        if x_freq >= threshold:\n            return x\n        else:\n            return -1\n```
[]