Segment tree
Intuition\n- Segment tree let\'s us query the number of elements greater than arr[i] in log(n) time by finding the sum of the elements in the right of arr[i].\n
# Intuition\n- Segment tree let\'s us query the number of elements greater than arr[i] in log(n) time by finding the sum of the elements in the right of arr[i].\n- Update is done by marking the specific element as 1.\n- Elements are mapped to reduce the size of numbers from 1e9 to 1e5. \n<!-- Describe your first thoughts on how to solve this problem. -->\n\n\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(n*log(n))$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nint sega[400000], segb[400000];\n\nint query(int seg[], int i, int l, int r, int ql, int qr) {\n    if (l >= ql && r <= qr) return seg[i];\n    if (l > qr || r < ql) return 0;\n    int mid = (l + r) / 2;\n    return query(seg, 2 * i + 1, l, mid, ql, qr) +\n           query(seg, 2 * i + 2, mid + 1, r, ql, qr);\n}\n\nvoid update(int seg[], int i, int l, int r, int idx, int val) {\n    if (l == r) {\n        seg[i] += val;\n        return;\n    }\n    int mid = (l + r) / 2;\n    if (idx <= mid)\n        update(seg, 2 * i + 1, l, mid, idx, val);\n    else\n        update(seg, 2 * i + 2, mid + 1, r, idx, val);\n    seg[i] = seg[2 * i + 1] + seg[2 * i + 2];\n}\n\nclass Solution {\n   public:\n    vector<int> resultArray(vector<int>& nums) {\n        // \\U0001f92c leetcode\n        memset(sega, 0, sizeof(sega));\n        memset(segb, 0, sizeof(segb));\n\n        int n = nums.size();\n\n        map<int, int> m;\n        vector<int> v = nums;\n        sort(v.begin(), v.end());\n        for (int i = 0; i < n; i++) {\n            if (i > 0 && v[i] == v[i - 1]) continue;\n            m[v[i]] = i;\n        }\n\n        int N = 100000;\n        vector<int> a = {nums[0]}, b = {nums[1]};\n        int ai = 0, bi = 0;\n        update(sega, 0, 0, N, m[nums[0]], 1);\n        update(segb, 0, 0, N, m[nums[1]], 1);\n\n        for (int i = 2; i < n; i++) {\n            int diff = query(sega, 0, 0, N, m[nums[i]] + 1, N) -\n                       query(segb, 0, 0, N, m[nums[i]] + 1, N);\n\n            if (diff > 0 || (diff == 0 && a.size() <= b.size())) {\n                a.push_back(nums[i]);\n                ai++;\n                update(sega, 0, 0, N, m[nums[i]], 1);\n            } else {\n                b.push_back(nums[i]);\n                bi++;\n                update(segb, 0, 0, N, m[nums[i]], 1);\n            }\n        }\n\n        for (int i = 0; i < bi + 1; i++) {\n            a.push_back(b[i]);\n        }\n        return a;\n    }\n};\n```
['C++']