[C++] Several solutions.
Random Sampling\n\n// Time Complexity: init O(n); query O(try_times * log(n)), try_times = 20\n// Space Complexity: O(n)\nclass MajorityChecker {\npublic:\n    
1. Random Sampling\n```\n// Time Complexity: init O(n); query O(try_times * log(n)), try_times = 20\n// Space Complexity: O(n)\nclass MajorityChecker {\npublic:\n    MajorityChecker(vector<int>& arr) : arr(arr) {\n        for (int i = 0; i < arr.size(); ++i) {\n            if (mp.find(arr[i]) == mp.end()) mp[arr[i]] = vector<int>(1, i);\n            else mp[arr[i]].push_back(i);\n        }\n        srand((unsigned) time(0));\n    }\n    \n    int query(int left, int right, int threshold) {\n        for (int i = 0; i < 20; ++i) {\n            int rand_i = rand() % (right - left + 1) + left;\n            int st_idx = lower_bound(mp[arr[rand_i]].begin(), mp[arr[rand_i]].end(), left)\n                    - mp[arr[rand_i]].begin();\n            int ed_idx = upper_bound(mp[arr[rand_i]].begin(), mp[arr[rand_i]].end(), right)\n                    - mp[arr[rand_i]].begin();\n            if (ed_idx - st_idx >= threshold) return arr[rand_i];\n        }\n        return -1;\n    }\nprivate:\n    unordered_map<int, vector<int>> mp;\n    vector<int> arr;\n};\n```\n\n2. Bucket method\n```\n// Time Complexity: init O(n), query O(sqrt(n) * log(n))\n// Space Complexity: O(n)\nclass MajorityChecker {\npublic:\n    MajorityChecker(vector<int>& arr) : arr(arr) {\n        if (arr.size() == 0) return ;\n        for (int i = 0; i < arr.size(); ++i) {\n            if (mp.find(arr[i]) == mp.end()) mp[arr[i]] = vector<int>(1, i);\n            else mp[arr[i]].push_back(i);\n        }\n        bucket_num = int(sqrt(arr.size()));\n        bucket_size = arr.size() / bucket_num;\n        bucket_major.resize(bucket_num + 1);\n        int major = 0, cot = 0;\n        for (int i = 0; i < arr.size(); ++i) {\n            if (i % bucket_size == 0) {\n                if (i > 0) bucket_major[(i - 1) / bucket_size] = major;\n                major = 0, cot = 0;\n            }\n            if (arr[i] == major) ++cot;\n            else if (cot > 0) --cot;\n            else major = arr[i], cot = 1;\n        }\n        bucket_major[(arr.size() - 1) / bucket_size] = major;\n    }\n    \n    int query(int left, int right, int threshold) {\n        int bucket_l = left / bucket_size, bucket_r = right / bucket_size, ret;\n        if (bucket_l == bucket_r) {\n            ret = major_num(left, right);\n            if (ret != -1 && count_occur(ret, left, right) >= threshold) return ret;\n        }\n        else {\n            ret = major_num(left, (bucket_l + 1) * bucket_size - 1);\n            if (count_occur(ret, left, right) >= threshold) return ret;\n            ret = major_num(bucket_r * bucket_size, right);\n            if (count_occur(ret, left, right) >= threshold) return ret;\n            for (int i = bucket_l + 1; i < bucket_r; ++i) {\n                if (count_occur(bucket_major[i], left, right) >= threshold) return bucket_major[i];\n            }\n        }\n        return -1;\n    }\nprivate:\n    int major_num(int l, int r) {\n        int major = 0, cot = 0;\n        for (int i = l; i <= r; ++i) {\n            if (arr[i] == major) ++cot;\n            else if (cot > 0) --cot;\n            else major = arr[i], cot = 1;\n        }\n        return major;\n    }\n\n    int count_occur(int val, int left, int right) {\n        int st_idx = lower_bound(mp[val].begin(), mp[val].end(), left)\n                - mp[val].begin();\n        int ed_idx = upper_bound(mp[val].begin(), mp[val].end(), right)\n                - mp[val].begin();\n        return ed_idx - st_idx;\n    }\n\n    unordered_map<int, vector<int>> mp;\n    vector<int> arr, bucket_major;\n    int bucket_num, bucket_size;\n};\n```\n\n3. Segment Tree\n```\n// Time Complexity: init O(n); query O(log(n) * log(n))\n// Space Complexity: O(n)\nclass MajorityChecker {\npublic:\n    MajorityChecker(vector<int>& arr) : arr(arr) {\n        if (arr.size() == 0) return ;\n        for (int i = 0; i < arr.size(); ++i) {\n            if (mp.find(arr[i]) == mp.end()) mp[arr[i]] = vector<int>(1, i);\n            else mp[arr[i]].push_back(i);\n        }\n        node.resize(4 * arr.size(), -1);\n        build(0, arr.size() - 1, 1);\n    }\n    \n    int query(int left, int right, int threshold) {\n        // index, occur\n        pair<int, int> ret = query(left, right, 0, arr.size() - 1, 1);\n        if (ret.second >= threshold) return ret.first;\n        else return -1;\n    }\nprivate:\n    void build(int st, int ed, int cur) {\n        if (st == ed) {\n            node[cur] = arr[st];\n            return ;\n        }\n        int mid = (st + ed) / 2;\n        build(st, mid, cur * 2);\n        build(mid + 1, ed, cur * 2 + 1);\n        if (node[cur * 2] != -1 && count_occur(node[cur * 2], st, ed) * 2 > ed - st + 1) {\n            node[cur] = node[cur * 2];\n        }\n        else if (node[cur * 2 + 1] != -1 && count_occur(node[cur * 2 + 1], st, ed) * 2 > ed - st + 1) {\n            node[cur] = node[cur * 2 + 1];\n        }\n        return ;\n    }\n\n    pair<int, int> query(const int &l, const int &r, int st, int ed, int cur) {\n        if (st > r || ed < l) {\n            return make_pair(-1, -1);\n        }\n        if (l <= st && ed <= r) {\n            if (node[cur] == -1) return make_pair(-1, -1);\n            int occ = count_occur(node[cur], l, r);\n            if (occ * 2 > r - l + 1) return make_pair(node[cur], occ);\n            else return make_pair(-1, -1);\n        }\n        int mid = (st + ed) / 2;\n        if (l <= mid) {\n            pair<int, int> ret_l = query(l, r, st, mid, cur * 2);\n            if (ret_l.first != -1) return ret_l;\n        }\n        if (r > mid) {\n            pair<int, int> ret_r = query(l, r, mid + 1, ed, cur * 2 + 1);\n            if (ret_r.first != -1) return ret_r;\n        }\n        return make_pair(-1, -1);\n    }\n\n    int count_occur(int val, int left, int right) {\n        int st_idx = lower_bound(mp[val].begin(), mp[val].end(), left)\n                - mp[val].begin();\n        int ed_idx = upper_bound(mp[val].begin(), mp[val].end(), right)\n                - mp[val].begin();\n        return ed_idx - st_idx;\n    }\n\n    unordered_map<int, vector<int>> mp;\n    vector<int> arr, node;\n};\n```
[]