Understandable O((lgN)^2) SegmentTree + TreeMap Java
Explanation:\nfor any interval [lo, hi], try to split it into lgN intervals which just fit into our segment tree\nlike (LCP: lowest common parent node)\n[9, 14]
Explanation:\nfor any interval [lo, hi], try to split it into lgN intervals which just fit into our segment tree\nlike (LCP: lowest common parent node)\n[9, 14] => [9], [10, 11], [12, 13], [14] => [9], [5: LCP node of 10, 11], [6], [14]\n[8, 14] => [8, 9, 10, 11], [12, 13], [14] => [2: LCP node 8, 9, 10, 11], [6], [14]\nthen we just do dummy check the candidate value on those nodes in segment tree, O(lgN) for each elements. so O(lgNlgN) for query.\nJava:\n```\nclass MajorityChecker {\n    public int len, level;\n    public Map<Integer, TreeMap<Integer, Integer>> prefixSum;\n    public int[] segmentTreeX;\n    public int[] segmentTreeY;\n    public MajorityChecker(int[] arr) {\n        len = arr.length;\n        prefixSum = new HashMap<>();\n        for(int i = 0; i < len; i++) {\n            if(!prefixSum.containsKey(arr[i])) prefixSum.put(arr[i], new TreeMap<>());\n            Integer find = prefixSum.get(arr[i]).lowerKey(i);\n            if(find == null) {\n                prefixSum.get(arr[i]).put(i, 1);\n            }\n            else {\n                prefixSum.get(arr[i]).put(i, 1 + prefixSum.get(arr[i]).get(find));\n            }\n        }\n        level = 1;\n        while((1 << (level - 1)) < len) {\n            level++;\n        }\n        segmentTreeX = new int[1 << level];\n        segmentTreeY = new int[1 << level];\n        for(int i = 0; i < len; i++) {\n            segmentTreeX[(1 << (level - 1)) + i] = arr[i];\n            segmentTreeY[(1 << (level - 1)) + i] = 1;\n        }\n        for(int i = ((1 << level) - 1)/2; i >= 1; i--) {\n            int left = segmentTreeX[i << 1];\n            int right = segmentTreeX[(i << 1) + 1];\n            int leftFreq = segmentTreeY[i << 1];\n            int rightFreq = segmentTreeY[(i << 1) + 1];\n            if(leftFreq >= rightFreq) {\n                if(left == right) {\n                    segmentTreeX[i] = left;\n                    segmentTreeY[i] = leftFreq + rightFreq;\n                }\n                else {\n                    segmentTreeX[i] = left;\n                    segmentTreeY[i] = leftFreq - rightFreq;\n                }\n            }\n            else {\n                if(left == right) {\n                    segmentTreeX[i] = right;\n                    segmentTreeY[i] = leftFreq + rightFreq;\n                }\n                else {\n                    segmentTreeX[i] = right;\n                    segmentTreeY[i] = rightFreq - leftFreq;\n                }\n            }\n        }\n    }\n    \n    public int query(int left, int right, int threshold) {\n        Set<Integer> candidates = new HashSet<>();\n        int i = left + (1 << (level - 1));\n        while(i <= right + (1 << (level - 1))) {\n            int step = 0;\n            while((i >> step) % 2 == 0) {\n                if(i + (1 << (step + 1)) > right + (1 << (level - 1))) {\n                    break;\n                }\n                step++;\n            }\n            candidates.add(segmentTreeX[i >> step]);\n            i += (1 << step);\n        }\n        //System.out.println(left + " " + right + ": " + (right - left + 1) + " "+candidates.size());\n        for(Integer c: candidates) {\n            int freq = 0;\n            if(prefixSum.get(c).containsKey(right)) {\n                freq += prefixSum.get(c).get(right);\n            }\n            else {\n                Integer find = prefixSum.get(c).lowerKey(right);\n                if(find != null) freq += prefixSum.get(c).get(find);\n            }\n            if(prefixSum.get(c).containsKey(left - 1)) {\n                freq -= prefixSum.get(c).get(left - 1);\n            }\n            else {\n                Integer find = prefixSum.get(c).lowerKey(left - 1);\n                if(find != null) freq -= prefixSum.get(c).get(find);\n            }\n            if(freq >= threshold) return c;\n        }\n        return -1;\n    }\n}\n\n/**\n * Your MajorityChecker object will be instantiated and called as such:\n * MajorityChecker obj = new MajorityChecker(arr);\n * int param_1 = obj.query(left,right,threshold);\n */   \n```\nScala:\n```\nclass MajorityChecker(_arr: Array[Int]) {\n    // segment tree + prefix sum\n    // segment interval into lgN parts, and use prefix sum to find out max in this lgN parts it takes O(lgN) for each equery\n    // O(lgNlgN) for query\n    // O(NlgN) for construction\n    \n    import collection.mutable.{Map, HashSet}\n    import java.util.TreeMap\n    \n    val len: Int = _arr.length\n    \n    // construct prefixSum\n    val prefixSum: Map[Int, TreeMap[Int, Int]] = Map()\n    for {\n        i <- 0 until len\n    } {\n        if(!prefixSum.contains(_arr(i))) prefixSum(_arr(i)) = new TreeMap()\n        if(prefixSum(_arr(i)).lowerKey(i) == null) {\n            prefixSum(_arr(i)).put(i, 1)\n        }\n        else {\n            val find = prefixSum(_arr(i)).lowerKey(i)\n            prefixSum(_arr(i)).put(i, 1 + prefixSum(_arr(i)).get(find))\n        }\n    }\n    \n    var level: Int =  1\n    while((1 << (level - 1)) < len) {\n        level += 1\n    }\n    \n    // construct segmentTree\n    val segmentTree: Array[(Int, Int)] = Array.fill((1 << level))((-1, 0)) // (element, frequency)\n    for {\n        i <- 0 until len\n    } {\n        segmentTree((1 << (level - 1)) + i) = (_arr(i), 1)\n    }\n    for {\n        i <- ((1 << level) - 1)/2 to 1 by -1\n    } {\n        val (left, leftFreq) = segmentTree(i * 2)\n        val (right, rightFreq) = segmentTree(i * 2 + 1)\n        if(leftFreq >= rightFreq) {\n            if(left != right) {\n                segmentTree(i) = (left, leftFreq - rightFreq)\n            }\n            else {\n                segmentTree(i) = (left, leftFreq + rightFreq)\n            }\n        }\n        else {\n            if(left != right) {\n                segmentTree(i) = (right, rightFreq - leftFreq)\n            }\n            else {\n                segmentTree(i) = (right, leftFreq + rightFreq)\n            }\n        }\n    }\n    \n    println(segmentTree.toList)\n    def query(left: Int, right: Int, threshold: Int): Int = {\n        // segment [left, right] into lgN part\n        val candidates: HashSet[Int] = HashSet()\n        var i: Int = left + (1 << (level - 1))\n        while(i <= right + (1 << (level - 1))) {\n            // try to find out maximum steps could go\n            var step: Int = 0\n            var isContinue: Boolean = true\n            while((i >> step) % 2 == 0 && isContinue) {\n                if(i + (1 << (step + 1)) <= right + (1 << (level - 1))) {\n                    step += 1\n                }\n                else {\n                    isContinue = false\n                }\n            }\n            // we could go [i, i + (1 << step) - 1], i = i + 1\n            candidates.add(segmentTree(i >> step)._1)\n            i = i + (1 << step)\n        }\n        for {\n            c <- candidates if c != -1\n        } {\n            var freq: Int = 0\n            if(prefixSum(c).containsKey(right)) {\n                freq += prefixSum(c).get(right)\n            }\n            else if(prefixSum(c).lowerKey(right) != null){\n                freq += prefixSum(c).get(prefixSum(c).lowerKey(right))\n            }\n            \n            if(prefixSum(c).containsKey(left - 1)) {\n                freq -= prefixSum(c).get(left - 1)\n            }\n            else if(prefixSum(c).lowerKey(left - 1) != null){\n                freq -= prefixSum(c).get(prefixSum(c).lowerKey(left - 1))\n            }\n            if(freq >= threshold) return c\n        }\n        return -1\n    }\n}\n\n/**\n * Your MajorityChecker object will be instantiated and called as such:\n * var obj = new MajorityChecker(arr)\n * var param_1 = obj.query(left,right,threshold)\n */\n ```
[]