Beats 100%, C++ Flat Segment Tree.
Approach\n1. Use Boyer Moore voting algorithm\n2. Use Segment Tree\n\n\n\n# Complexity\n- Time complexity:\nQuery - O(log n)\nBuild - O(n)\n- Space complexity: 
# Approach\n1. [Use Boyer Moore voting algorithm](https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm)\n2. Use Segment Tree\n\n![image.png](https://assets.leetcode.com/users/images/a2229dc9-5655-4e08-ae0e-9fefbd927c4e_1703624154.31403.png)\n\n# Complexity\n- Time complexity:\nQuery - $$O(log n)$$\nBuild - $$O(n)$$\n- Space complexity: $$O(n)$$\n\n# Code\n```\nclass MajorityChecker {\n    static constexpr int N = 2 * 1e4 + 1; \n    struct SegmentTree {\n\n        struct Element {\n            int majority;\n            int count;\n        };\n\n        static constexpr Element merge(const Element& l, const Element& r) noexcept {\n            if(l.majority == r.majority) return {l.majority, l.count + r.count};\n            if(l.count > r.count) return {l.majority, l.count - r.count};\n            return {r.majority, r.count - l.count};\n        }\n\n        explicit SegmentTree(int n) : n(n), t(2*n + 2) {}\n\n        void build(const auto& arr) noexcept {\n            for(int i = 0; i < n; ++i) {\n               t[i + n] = Element{arr[i], 1};\n            }\n\n            for(int i = n - 1; i > 0; --i) {\n                t[i] = merge(t[i << 1], t[i << 1 | 1]);\n            }\n        }\n\n        Element query(int l, int r) const noexcept {\n            Element result{0, 0};\n            for(l += n, r += n; l <= r; l >>= 1, r >>= 1) {\n                if(l & 1) result = merge(result, t[l++]);\n                if(!(r & 1)) result = merge(result, t[r--]);\n            }\n            return result;\n        }\n\n        private:\n        int n;\n        std::vector<Element> t;\n    };\n\npublic:\n    MajorityChecker(vector<int>& arr) : tree(arr.size()), indices(N) {\n        for (int i = 0; i < arr.size(); ++i) indices[arr[i]].push_back(i);\n        tree.build(arr);\n    }\n\n    int query(int left, int right, int threshold) const noexcept {\n        const auto candidate = tree.query(left, right);\n        if(candidate.majority == 0) {\n            return -1;\n        }\n        const auto& candidate_idxs = indices[candidate.majority];\n        const int l = std::ranges::lower_bound(candidate_idxs, left) - candidate_idxs.begin();\n        const int r = std::ranges::upper_bound(candidate_idxs, right) - candidate_idxs.begin();\n\n        return (r - l) < threshold ? -1 : candidate.majority;\n    }\nprivate:\n SegmentTree tree;\n vector<vector<int>> indices;\n};\n```
['C++']