c# segment Tree
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```\npublic class MajorityChecker {\n    public class SegmentTree\n    {\n        public SegmentTree left, right;\n        public int start, end;\n        //info\n        public int val, freqDiff; //the possible major num and its possible freDiff than others\n        public SegmentTree(int a, int b)\n        {\n            start = a;\n            end = b;\n            val = 0;\n            freqDiff = 0; \n        }\n    }\n    void Init(SegmentTree node, int a, int b)\n    {\n        if(a == b)\n        {\n            node.val = arr[a];\n            node.freqDiff = 1;\n            return;\n        }\n        int mid = (a + b) / 2;\n        if(node.left == null)\n        {\n            node.left = new SegmentTree(a, mid);\n            node.right = new SegmentTree(mid+1, b);\n        }\n\n        Init(node.left, a, mid);\n        Init(node.right, mid+1, b);\n\n        if(node.left.val == node.right.val)\n        {\n            node.val = node.left.val;\n            node.freqDiff = node.left.freqDiff + node.right.freqDiff;\n        }\n        else if(node.left.freqDiff > node.right.freqDiff)\n        {\n            node.val = node.left.val;\n            node.freqDiff = node.left.freqDiff - node.right.freqDiff;\n        }\n        else\n        {\n            node.val = node.right.val;\n            node.freqDiff = node.right.freqDiff - node.left.freqDiff;\n        }\n    }\n\n    public (int, int) QueryRange(SegmentTree node, int a, int b)\n    {\n        if(b < node.start || a > node.end) return ((0, 0));\n        if(a <= node.start && b >= node.end) return ((node.val, node.freqDiff));\n        var L = QueryRange(node.left, a, b);\n        var R = QueryRange(node.right, a, b);\n\n        if(L.Item1 == R.Item1)\n        {\n            return ((L.Item1, L.Item2 + R.Item2));\n        }\n        else if(L.Item2 >= R.Item2)\n        {\n            return ((L.Item1, L.Item2 - R.Item2));\n        }\n        else return ((R.Item1, R.Item2 - L.Item2));\n    }\n\n    Dictionary<int, List<int>> dict;//val-> all index\n    int[] arr;\n    SegmentTree seg;\n    public MajorityChecker(int[] arr) {\n        int n = arr.Length;\n        this.arr = arr;\n        seg = new SegmentTree(0, n-1);\n        dict = new();\n        Init(seg, 0, n-1);\n        for(int i=0; i<arr.Length; ++i)\n        {\n            if(!dict.ContainsKey(arr[i])) dict[arr[i]] = new();\n            dict[arr[i]].Add(i);\n        }\n    }\n    \n    public int Query(int left, int right, int threshold) {\n        (int val, int freqDif) = QueryRange(seg, left, right);\n        if(!dict.ContainsKey(val)) return -1;\n        int a = LowerBound(dict[val], left);\n        int b = UpperBound(dict[val], right);\n        int count = b-a;\n        if(count >= threshold) return val;\n        return -1;\n    }\n\n    public int UpperBound(List<int> ls, int x)\n    {\n        (int l, int r) = (0, ls.Count);\n        while(l < r)\n        {\n            int mid = l + (r - l) / 2;\n            if(x >= ls[mid]) l = mid + 1;\n            else r = mid;\n        }\n        return l;\n    }\n\n    public int LowerBound(List<int> ls, int x)\n    {\n        (int l, int r) = (0, ls.Count);\n        while(l < r)\n        {\n            int mid = l + (r - l) / 2;\n            if(x <= ls[mid]) r = mid;\n            else l = mid + 1;\n        }\n        return l;\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```
['C#']