Java log(n) construction (log(n))^2 query
Basic idea is to build a segment tree where each node stores the major element (element that appears > half the array size) within the segment on that node. Whe
Basic idea is to build a segment tree where each node stores the major element (element that appears > half the array size) within the segment on that node. When combining 2 segments into the parent node, the major element of the parent node has to be either of the 2 child-segment\'s major elements. To find out which one is the real major element for the parent node, we need a fast way to count the number of appearances of an element given a range.\n\nThis is done by preprocessing the entire array and put the index and count of appearances on the left of the index in a tree map, which gives us log(n) time for computing the number of appearances within any range. Searching the segment tree takes log(n), while merging 2 nodes can take up to log(n) as well, so overall (log(n))^2. I know my idea is not as fast as the Moore+segment tree solution which achieves log(n) query time but I thought it\'d be useful to share another solution.\n\n```\nimport java.util.*;\nimport java.util.Map.Entry;\n\nclass MajorityChecker {\n    class Node {\n        int l, r;\n        int maj;\n        Node left, right;\n        public Node(int l, int r, int maj, Node left, Node right) {\n            this.l=l;\n            this.r = r;\n            this.maj = maj;\n            this.left = left;\n            this.right = right;\n        }\n        public Node() {}\n    }\n    int [] arr;\n    int n;\n    // for each element, store the indices where it appears, and the count of appearances on its left (inclusive)\n    HashMap<Integer, TreeMap<Integer, Integer>> left_cnt = new HashMap<>();\n    // segment tree node\n    Node root;\n    public MajorityChecker(int[] arr) {\n        this.arr = arr;\n        n = arr.length;\n        for (int i = 0; i < n; i++) {\n            if (!left_cnt.containsKey(arr[i])) {\n                left_cnt.put(arr[i], new TreeMap<>());\n            }\n            TreeMap<Integer, Integer> ind_to_cnt = left_cnt.get(arr[i]);\n            Entry<Integer, Integer> ent = ind_to_cnt.lastEntry();\n            if (ent == null) ind_to_cnt.put(i, 1);\n            else ind_to_cnt.put(i, ent.getValue()+1);\n        }\n        root = build_tree(0, n-1);\n    }\n    Node build_tree(int left, int right) {\n        if (left == right) {\n            return new Node(left, right, arr[left], null, null);\n        }\n        int mid = left + (right - left) / 2;\n        Node node = new Node();\n        node.l = left;\n        node.r = right;\n        node.left = build_tree(left, mid);\n        node.right = build_tree(mid+1, right);\n        int left_maj = node.left.maj, right_maj = node.right.maj;\n        if (left_maj == right_maj) {\n            node.maj = left_maj;\n            return node;\n        }\n        int count_left_maj = count(left, right, left_maj);\n        int count_right_maj = count(left, right, right_maj);\n        if (2 * count_left_maj > (right - left + 1)) node.maj = left_maj;\n        else if (2 * count_right_maj > (right - left + 1)) node.maj = right_maj;\n        else node.maj = -1;\n        return node;\n    }\n    int count(int left, int right, int val) {\n        /* count appearances of val in [left, right] */\n        if (!left_cnt.containsKey(val)) return 0;\n        \n        TreeMap<Integer, Integer> ind_to_cnt = left_cnt.get(val);\n        Entry<Integer, Integer> ent_left = ind_to_cnt.floorEntry(left-1);\n        Entry<Integer, Integer> ent_right = ind_to_cnt.floorEntry(right);\n        \n        int cnt_left = ent_left == null ? 0 : ent_left.getValue();\n        int cnt_right = ent_right == null ? 0 : ent_right.getValue();\n        \n        return cnt_right - cnt_left;\n    }\n    \n    public int query(int left, int right, int threshold) {\n        int maj = get_maj(left, right, root);\n        if (maj == -1) return -1;\n        int cnt = count(left, right, maj);\n        if (cnt >= threshold) return maj;\n        return -1;\n    }\n    int get_maj(int left, int right, Node node) {\n        // single number case\n        if (node.l == left && node.r == right) return node.maj;\n        \n        // try to split [left, right]\n        int mid = node.l + (node.r - node.l) / 2;\n        if (mid >= right) return get_maj(left, right, node.left);\n        if (mid < left) return get_maj(left, right, node.right);\n        \n        // merge major element from left and right child-nodes\n        int left_maj = get_maj(left, mid, node.left);\n        int right_maj = get_maj(mid+1, right, node.right);\n        \n        if (left_maj == right_maj) return left_maj;\n        \n        int count_left_maj = count(left, right, left_maj);\n        if (2 * count_left_maj > (right - left + 1)) return left_maj;\n        \n        int count_right_maj = count(left, right, right_maj);\n        if (2 * count_right_maj > (right - left + 1)) return right_maj;\n        \n        return -1;\n    }\n\n}\n```
[]