[C++/Java/Python] O(log(n)) per query using Segment Tree + Binary Search
This solution is inspired by lee215\'s 3rd solution.\n\nPrerequisite knowledges:\n1. Boyer\u2013Moore majority vote algorithm in LeetCode 169: Majority Element\
This solution is inspired by [lee215\'s 3rd solution](https://leetcode.com/problems/online-majority-element-in-subarray/discuss/355848/Python-Random-Draft-+-Binary-Search).\n\nPrerequisite knowledges:\n1. **Boyer\u2013Moore majority vote algorithm** in [LeetCode 169: Majority Element](https://leetcode.com/problems/majority-element/solution/)\n2. **Segment Tree** in [LeetCode 307: Range Sum Query - Mutable](https://leetcode.com/problems/range-sum-query-mutable/solution/)\n\nThe problem statements already guaranteed that if there\'s an answer, that answer should be the **majority vote** in that given subarray.\n\nGiven any subarray\'s range, we can get its majority vote in **O(log(n)) time** using **Segment Tree**:\n* For each node X in the Segment Tree, we maintain the majority vote of the node X\'s corressponding subarray\'s range.\n* By applying the same idea in the **Boyer-Moore majority vote algorithm**, we can merge two majority votes came from two different subarray\'s ranges into a single majority vote.\n\nAfter getting the majority vote M in that given subarray\'s range, we still need to count how many times M occurred in that given subarray\'s range.\nIf M occurs T times where T >= threshold, then M is the answer. Otherwise, there\'s no answer (i.e. should return -1).\n\nWe can count how many times M occurred in that given subarray\'s range in **O(log(n)) time** using **Binary Search**:\n* For each values V in the input array A, we pre-calculate all the indices that V occurs.\n* For each query, given a majority vote M, we can do two binary searches for the first M\'s index >= left, and the first M\'s index > right. The distance between two binary searches\' result is the number of times M occured.\n\n**C++ solution:** [segment-tree-solution.cpp](https://github.com/gengyouchen/leetcode/blob/master/online-majority-element-in-subarray/segment-tree-solution.cpp)\n```\nclass RangeMajorityVoteQuery {\nprivate:\n\tstruct MajorityVote { int num, vote; };\n\tstatic MajorityVote merge(const MajorityVote& a, const MajorityVote& b) {\n\t\tMajorityVote ret;\n\t\tret.num = (a.vote > b.vote) ? a.num : b.num;\n\t\tret.vote = (a.num == b.num) ? (a.vote + b.vote) : abs(a.vote - b.vote);\n\t\treturn ret;\n\t}\n\n\tvector<MajorityVote> segTree;\npublic:\n\tRangeMajorityVoteQuery(const vector<int>& A) {\n\t\tconst int n = A.size();\n\t\tint nLeaf = 1;\n\t\twhile (nLeaf < n)\n\t\t\tnLeaf *= 2;\n\t\tsegTree.resize(nLeaf * 2);\n\n\t\tfor (int i = 0; i < n; ++i)\n\t\t\tsegTree[nLeaf + i] = {A[i], 1};\n\n\t\tfor (int x = nLeaf - 1; x > 0; --x)\n\t\t\tsegTree[x] = merge(segTree[x * 2], segTree[x * 2 + 1]);\n\t}\n\tint query(int i, int j) const {\n\t\tconst int nLeaf = segTree.size() / 2;\n\t\tint x = nLeaf + i, y = nLeaf + j;\n\n\t\tauto ret = merge(segTree[x], segTree[y]);\n\t\twhile (x / 2 != y / 2) {\n\t\t\tif (!(x % 2))\n\t\t\t\tret = merge(ret, segTree[x + 1]);\n\t\t\tif (y % 2)\n\t\t\t\tret = merge(ret, segTree[y - 1]);\n\t\t\tx /= 2, y /= 2;\n\t\t}\n\n\t\tif (!ret.vote)\n\t\t\treturn -1; /* failed */\n\t\treturn ret.num;\n\t}\n};\n\nclass MajorityChecker {\nprivate:\n\tRangeMajorityVoteQuery q;\n\tunordered_map<int, vector<int>> val2idx;\npublic:\n\t/* time: O(n), space: O(n) */\n\tMajorityChecker(const vector<int>& arr) : q(arr) {\n\t\tconst int n = arr.size();\n\t\tfor (int i = 0; i < n; ++i)\n\t\t\tval2idx[arr[i]].push_back(i);\n\t}\n\n\t/* time: O(log(n)), space: O(1) auxiliary */\n\tint query(int left, int right, int threshold) const {\n\t\tconst int majorityVote = q.query(left, right);\n\t\tif (majorityVote == -1)\n\t\t\treturn -1;\n\n\t\tconst auto& idx = val2idx.at(majorityVote);\n\t\tconst auto L = lower_bound(idx.begin(), idx.end(), left);\n\t\tconst auto R = upper_bound(idx.begin(), idx.end(), right);\n\t\tconst int count = distance(L, R);\n\t\tif (count < threshold)\n\t\t\treturn -1;\n\n\t\treturn majorityVote;\n\t}\n};\n```\n\n**Java Solution:** [segment-tree-solution.java](https://github.com/gengyouchen/leetcode/blob/master/online-majority-element-in-subarray/segment-tree-solution.java)\n* Java doesn\'t have built-in lower_bound/upper_bound functions, so we need to manually implement these two binary searches.\n```\nclass RangeMajorityVoteQuery {\n\tprivate static class MajorityVote {\n\t\tpublic int num = 0, vote = 0;\n\t}\n\tprivate static MajorityVote merge(MajorityVote a, MajorityVote b) {\n\t\tMajorityVote ret = new MajorityVote();\n\t\tret.num = (a.vote > b.vote) ? a.num : b.num;\n\t\tret.vote = (a.num == b.num) ? (a.vote + b.vote) : Math.abs(a.vote - b.vote);\n\t\treturn ret;\n\t}\n\n\tprivate MajorityVote[] segTree;\n\tpublic RangeMajorityVoteQuery(int[] A) {\n\t\tfinal int n = A.length;\n\t\tint nLeaf = 1;\n\t\twhile (nLeaf < n)\n\t\t\tnLeaf *= 2;\n\t\tsegTree = new MajorityVote[nLeaf * 2];\n\n\t\tfor (int i = 0; i < nLeaf; ++i) {\n\t\t\tMajorityVote node = new MajorityVote();\n\t\t\tif (i < n) {\n\t\t\t\tnode.num = A[i];\n\t\t\t\tnode.vote = 1;\n\t\t\t}\n\t\t\tsegTree[nLeaf + i] = node;\n\t\t}\n\n\t\tfor (int x = nLeaf - 1; x > 0; --x)\n\t\t\tsegTree[x] = merge(segTree[x * 2], segTree[x * 2 + 1]);\n\t}\n\tpublic int query(int i, int j) {\n\t\tfinal int nLeaf = segTree.length / 2;\n\t\tint x = nLeaf + i, y = nLeaf + j;\n\n\t\tMajorityVote ret = merge(segTree[x], segTree[y]);\n\t\twhile (x / 2 != y / 2) {\n\t\t\tif (x % 2 == 0)\n\t\t\t\tret = merge(ret, segTree[x + 1]);\n\t\t\tif (y % 2 == 1)\n\t\t\t\tret = merge(ret, segTree[y - 1]);\n\t\t\tx /= 2;\n\t\t\ty /= 2;\n\t\t}\n\n\t\tif (ret.vote == 0)\n\t\t\treturn -1; /* failed */\n\t\treturn ret.num;\n\t}\n}\n\nclass MajorityChecker {\n\tprivate RangeMajorityVoteQuery q;\n\tprivate HashMap<Integer, ArrayList<Integer>> val2idx;\n\tprivate static int lowerBound(ArrayList<Integer> A, int x) {\n\t\tint L = 0, R = A.size();\n\t\twhile (L < R) {\n\t\t\tfinal int mid = L + (R - L) / 2;\n\t\t\tif (A.get(mid) >= x)\n\t\t\t\tR = mid;\n\t\t\telse\n\t\t\t\tL = mid + 1;\n\t\t}\n\t\treturn L;\n\t}\n\tprivate static int upperBound(ArrayList<Integer> A, int x) {\n\t\tint L = 0, R = A.size();\n\t\twhile (L < R) {\n\t\t\tfinal int mid = L + (R - L) / 2;\n\t\t\tif (A.get(mid) > x)\n\t\t\t\tR = mid;\n\t\t\telse\n\t\t\t\tL = mid + 1;\n\t\t}\n\t\treturn L;\n\t}\n\t/* time: O(n), space: O(n) */\n\tpublic MajorityChecker(int[] arr) {\n\t\tfinal int n = arr.length;\n\t\tq = new RangeMajorityVoteQuery(arr);\n\t\tval2idx = new HashMap<Integer, ArrayList<Integer>>();\n\t\tfor (int i = 0; i < n; ++i) {\n\t\t\tif (!val2idx.containsKey(arr[i]))\n\t\t\t\tval2idx.put(arr[i], new ArrayList<Integer>());\n\t\t\tArrayList<Integer> idx = val2idx.get(arr[i]);\n\t\t\tidx.add(i);\n\t\t}\n\t}\n\t/* time: O(log(n)), space: O(1) auxiliary */\n\tpublic int query(int left, int right, int threshold) {\n\t\tfinal int majorityVote = q.query(left, right);\n\t\tif (majorityVote == -1)\n\t\t\treturn -1;\n\n\t\tArrayList<Integer> idx = val2idx.get(majorityVote);\n\t\tfinal int L = lowerBound(idx, left);\n\t\tfinal int R = upperBound(idx, right);\n\t\tfinal int count = R - L;\n\t\tif (count < threshold)\n\t\t\treturn -1;\n\n\t\treturn majorityVote;\n\t}\n}\n```\n\n**Python solution:** [segment-tree-solution.py](https://github.com/gengyouchen/leetcode/blob/master/online-majority-element-in-subarray/segment-tree-solution.py)\n* This O(log(n)) algorithm performs badly when translated to Python. You can do further optimizations to reduce large time constant. I won\'t do it here unless it can improve time complexity.\n```\nclass RangeMajorityVoteQuery:\n\tclass MajorityVote:\n\t\tnum = 0\n\t\tvote = 0\n\tdef merge(self, a: MajorityVote, b: MajorityVote) -> MajorityVote:\n\t\tret = self.MajorityVote()\n\t\tret.num = a.num if a.vote > b.vote else b.num\n\t\tret.vote = a.vote + b.vote if a.num == b.num else abs(a.vote - b.vote)\n\t\treturn ret;\n\n\tdef __init__(self, A: List[int]):\n\t\tself.segTree = []\n\t\tnLeaf = 1;\n\t\twhile nLeaf < len(A):\n\t\t\tnLeaf *= 2;\n\t\tfor i in range(nLeaf * 2):\n\t\t\tnode = self.MajorityVote()\n\t\t\tself.segTree.append(node)\n\n\t\tfor i in range(len(A)):\n\t\t\tnode = self.segTree[nLeaf + i]\n\t\t\tnode.num, node.vote = A[i], 1\n\n\t\tfor x in range(nLeaf - 1, 0, -1):\n\t\t\tself.segTree[x] = self.merge(self.segTree[x * 2], self.segTree[x * 2 + 1])\n\n\tdef query(self, i: int, j: int) -> int:\n\t\tnLeaf = len(self.segTree) // 2\n\t\tx, y = nLeaf + i, nLeaf + j\n\n\t\tret = self.merge(self.segTree[x], self.segTree[y]);\n\t\twhile x // 2 != y // 2:\n\t\t\tif x % 2 == 0:\n\t\t\t\tret = self.merge(ret, self.segTree[x + 1])\n\t\t\tif y % 2 == 1:\n\t\t\t\tret = self.merge(ret, self.segTree[y - 1])\n\t\t\tx //= 2\n\t\t\ty //= 2\n\n\t\tif ret.vote == 0:\n\t\t\treturn -1; # failed\n\t\treturn ret.num\n\nclass MajorityChecker:\n\t# time: O(n), space: O(n)\n\tdef __init__(self, arr: List[int]):\n\t\tself.q = RangeMajorityVoteQuery(arr)\n\t\tself.val2idx = {}\n\t\tfor i in range(len(arr)):\n\t\t\tself.val2idx.setdefault(arr[i], []).append(i)\n\n\t# time: O(log(n)), space: O(1) auxiliary\n\tdef query(self, left: int, right: int, threshold: int) -> int:\n\t\tmajorityVote = self.q.query(left, right)\n\t\tif majorityVote == -1:\n\t\t\treturn -1\n\t\tidx = self.val2idx.get(majorityVote)\n\t\tL = bisect.bisect_left(idx, left)\n\t\tR = bisect.bisect_right(idx, right)\n\t\tcount = R - L\n\t\tif count < threshold:\n\t\t\treturn -1\n\t\treturn majorityVote\n```
[]