Solution Online Majority Element In Subarray
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nfunction SegmentTreeRQ(m, A, n) {\n    let h = Math.ceil(Math.log2(n));\n    const MAX = 2 * 2 ** h - 1;\n    let tree = Array(MAX).fill(-1);\n    let a = [...A];\n    build(1, 0, n - 1);\n    return {query}\n    function build(vi, tl, tr) {\n        if (tl == tr) {\n            tree[vi] = a[tl];\n            return;\n        }\n        let mid = getMid(tl, tr);\n        build(vi * 2, tl, mid);\n        build(vi * 2 + 1, mid + 1, tr);\n        if (tree[vi * 2] != -1 && get_occurrence(tree[vi * 2], tl, tr) * 2 > tr - tl + 1) {\n            tree[vi] = tree[vi * 2];\n        } else if (tree[vi * 2 + 1] != -1 && get_occurrence(tree[vi * 2 + 1], tl, tr) * 2 > tr - tl + 1) {\n            tree[vi] = tree[vi * 2 + 1];\n        }\n    }\n\n    function query(vi, l, r, tl, tr) {\n        if (l > tr || r < tl) {\n            return {\n                first: -1,\n                second: -1\n            };\n        }\n        if (tl <= l && r <= tr) {\n            if (tree[vi] == -1) return {\n                first: -1,\n                second: -1\n            };\n            let occ = get_occurrence(tree[vi], tl, tr);\n            if (occ * 2 > tr - tl + 1) {\n                return {\n                    first: tree[vi],\n                    second: occ\n                };\n            } else {\n                return {\n                    first: -1,\n                    second: -1\n                };\n            }\n        }\n        let mid = getMid(l, r);\n        let resL = query(vi * 2, l, mid, tl, tr);\n        if (resL.first > -1) return resL;\n        let resR = query(vi * 2 + 1, mid + 1, r, tl, tr);\n        if (resR.first > -1) return resR;\n        return {\n            first: -1,\n            second: -1\n        };\n    }\n\n    function get_occurrence(num, l, r) {\n        if (!m.has(num)) return 0;\n        let a = m.get(num);\n        let lbv = lower_bound(a, l);\n        if (lbv == a.length) return 0;\n        let ubv = upper_bound(a, r);\n        return ubv - lbv;\n    }\n\n    function lower_bound(a, t) {\n        let low = 0;\n        let n = a.length;\n        let high = n - 1;\n        while (low < high) {\n            let mid = getMid(low, high);\n            if (a[mid] < t) {\n                low = mid + 1;\n            } else if (a[mid] > t) {\n                high = mid;\n            } else {\n                return mid;\n            }\n        }\n        return high;\n    }\n    \n    function upper_bound(a, t) { \n        let n = a.length;\n        for (let i = 0; i < n; i++) {\n            if (a[i] > t) return i;\n        }\n        return n;\n    }\n\n    function getMid(low, high) {\n        return low + (high - low >> 1);\n    }\n}\n\nfunction MajorityChecker(a) {\n    let m = new Map();\n    let n = a.length;\n    for (let i = 0; i < n; i++) {\n        if (!m.has(a[i])) m.set(a[i], []);\n        m.get(a[i]).push(i);\n    }\n    let st = new SegmentTreeRQ(m, a, n);\n    return {\n        query\n    }\n\n    function query(left, right, threshold) {\n        let res = st.query(1, 0, n - 1, left, right);\n        if (res.second >= threshold) {\n            return res.first;\n        }\n        return -1;\n    }\n}\n```
['JavaScript']