[Java][Segment Tree] Easy to understand, beat 99%
Time:\n\t- initialization: O(N)\n\t- query: O(logN)\n- Space: O(N)\n\nUpdated:\nThanks to @shuiyong add more detailed explanation\n\n\nclass MajorityChecker {\n
- **Time:**\n\t- initialization: `O(N)`\n\t- query: `O(logN)`\n- **Space:** `O(N)`\n\n**Updated:**\nThanks to @shuiyong add more [**detailed explanation**](https://leetcode.com/problems/online-majority-element-in-subarray/discuss/466221/JavaSegment-Tree-Easy-to-understand-beat-99/455572)\n\n```\nclass MajorityChecker {\n    private int[] nums;\n    private SegmentTreeNode treeRoot;\n    private Map<Integer, List<Integer>> idxMap;\n\n    public MajorityChecker(int[] nums) {\n        this.nums = nums;\n        this.idxMap = new HashMap<>();\n        this.treeRoot = buildTree(0, nums.length - 1, nums);\n\n        for (int i = 0; i < nums.length; ++i) {\n            List<Integer> idxList = idxMap.get(nums[i]);\n            if (idxList == null) {\n                idxList = new ArrayList<>();\n                idxMap.put(nums[i], idxList);\n            }\n            idxList.add(i);\n        }\n    }\n    \n    public int query(int left, int right, int threshold) {\n        Pair cand = queryTree(treeRoot, left, right);\n        if (cand.freq >= threshold) {\n            return cand.val;\n        }\n\n        // According to Java Collections.binarySearch API:\n        // if key doesn\'t exist in the list, will return: -(insertion point) - 1\n        int leftIdx = Collections.binarySearch(idxMap.get(cand.val), left);\n        if (leftIdx < 0) {\n            leftIdx = -leftIdx - 1;\n        }\n\n        int rightIdx = Collections.binarySearch(idxMap.get(cand.val), right);\n        if (rightIdx < 0) {\n            rightIdx = -rightIdx - 2;\n        }\n\n        if (rightIdx - leftIdx + 1 >= threshold) {\n            return cand.val;\n        }\n\n        return -1;\n    }\n\n    //////////////////////////////////////////////\n    // following code is SegmentTree related stuff\n    private SegmentTreeNode buildTree(int start, int end, int[] nums) {\n        if (start == end) {\n            return new SegmentTreeNode(start, end, new Pair(nums[start], 1));\n        }\n\n        SegmentTreeNode root = new SegmentTreeNode(start, end, null);\n\n        int mid = start + (end - start) / 2;\n        root.left = buildTree(start, mid, nums);\n        root.right = buildTree(mid + 1, end, nums);\n        root.pair = mergePair(root.left.pair, root.right.pair);\n\n        return root;\n    }\n\n    private Pair queryTree(SegmentTreeNode root, int start, int end) {\n        if (start <= root.start && root.end <= end) {\n            return root.pair;\n        }\n\n        Pair res = new Pair(0, 0);\n        int mid = root.start + (root.end - root.start) / 2;\n        if (start <= mid) {\n            res = mergePair(res, queryTree(root.left, start, end));\n        }\n        if (mid < end) {\n            res = mergePair(res, queryTree(root.right, start, end));\n        }\n\n        return res;\n    }\n\n    private Pair mergePair(Pair pair1, Pair pair2) {\n        if (pair1.val == pair2.val) {\n            return new Pair(pair1.val, pair1.freq + pair2.freq);\n        }\n\n        if (pair1.freq > pair2.freq) {\n            return new Pair(pair1.val, pair1.freq - pair2.freq);\n        }\n\n        return new Pair(pair2.val, pair2.freq - pair1.freq);\n    }\n\n    static class SegmentTreeNode {\n        int start;\n        int end;\n        Pair pair;\n        SegmentTreeNode left;\n        SegmentTreeNode right;\n\n        SegmentTreeNode(int start, int end, Pair pair) {\n            this.start = start;\n            this.end = end;\n            this.pair = pair;\n            this.left = null;\n            this.right = null;\n        }\n    }\n\n    static class Pair {\n        int val;\n        int freq;\n\n        Pair(int val, int freq) {\n            this.val = val;\n            this.freq = freq;\n        }\n    }\n}\n```
[]