Fenwick Tree || O(NlogN) Solution || C++
Intuition\n Describe your first thoughts on how to solve this problem. \nReference: https://www.bilibili.com/video/BV14r421W7oR/ \n\n# Approach\n Describe your 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nReference: https://www.bilibili.com/video/BV14r421W7oR/ \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nUse a fenwick tree to store the "counting information" of all elements. Each "greaterCount" operation is of complexity O(logN), and each time we insert an element to the tree, the time complexity is also O(logN).\n\nUse binary search to map a number of 1 ~ 10^9 into 1 - n. The time complexity of index mapping is O(logN)\n\n# Complexity\n- Time complexity: **O(NlogN)**\n\n- Space complexity: **O(N)**\n\n# Code\n```\nclass Fenwick {\nprivate:\n    vector<int> tree;\npublic:\n    Fenwick (int n) : tree(vector<int>(n + 1, 0)) {}\n\n    int prefixSum(int x) {\n        // return the prefix sum of [1, x]\n        int sum = 0;\n        while (x > 0) {\n            sum += tree[x];\n            x = x - (x & (-x));\n        }\n        return sum;\n    }\n\n    void update(int x) {\n        // insert an element of index-x\n        while (x < tree.size()) {\n            tree[x]++;\n            x = x + (x & (-x));\n        }\n    }\n};\n\nclass Solution {\npublic:\n    int greaterCount(Fenwick& tree, int idx, int cnt) {\n        return cnt - tree.prefixSum(idx);\n    }\n\n    int binarySearch(vector<int>& numsSorted, int val) {\n        return std::lower_bound(numsSorted.begin(), numsSorted.end(), val) - numsSorted.begin();\n    }\n\n    vector<int> resultArray(vector<int>& nums) {\n        int n = nums.size();\n\n        // compress num to index (1-indexed)\n        vector<int> numsSorted = nums;\n        std::sort(numsSorted.begin(), numsSorted.end());\n\n        vector<int> arr1;\n        vector<int> arr2;\n        arr1.push_back(nums[0]);\n        arr2.push_back(nums[1]);\n\n        Fenwick t1(n);\n        Fenwick t2(n);\n        t1.update(binarySearch(numsSorted, nums[0]) + 1);\n        t2.update(binarySearch(numsSorted, nums[1]) + 1);\n\n        for (int i = 2; i < n; i++) {\n            int idx = binarySearch(numsSorted, nums[i]) + 1;\n            int gc1 = greaterCount(t1, idx, arr1.size());\n            int gc2 = greaterCount(t2, idx, arr2.size());\n            if (gc1 < gc2 || (gc1 == gc2 && arr1.size() > arr2.size())) {\n                t2.update(idx);\n                arr2.push_back(nums[i]);\n            } else {\n                t1.update(idx);\n                arr1.push_back(nums[i]);\n            }\n        }\n\n        arr1.insert(arr1.end(), arr2.begin(), arr2.end());\n        return arr1;\n    }\n};\n```
['C++']