[C++] Range Compression with Fenwick tree (BIT), with comments
Complexity\n- Time complexity:\nO(NLogN)\n\n- Space complexity:\nO(N)\n\n# Code\n\n\nclass Solution {\npublic:\n    int N;\n    vector<int> BIT1, BIT2;\n\n    /
# Complexity\n- Time complexity:\nO(NLogN)\n\n- Space complexity:\nO(N)\n\n# Code\n```\n\nclass Solution {\npublic:\n    int N;\n    vector<int> BIT1, BIT2;\n\n    // Had to create separate methods for arr1\'s BIT and arr2\'s BIT to optimize space, passing by reference consumes extra memory\n\n    void update1(int ind, int delta) {\n        for (;ind < N; ind += (ind&-ind)) {\n            BIT1[ind] += delta;\n        }\n    }\n\n    int query1(int ind) {\n        int sum = 0;\n        for (;ind > 0; ind -= (ind&-ind)) {\n            sum += BIT1[ind];\n        }\n        return sum;\n    }\n\n    void update2(int ind, int delta) {\n        for (;ind < N; ind += (ind&-ind)) {\n            BIT2[ind] += delta;\n        }\n    }\n\n    int query2(int ind) {\n        int sum = 0;\n        for (;ind > 0; ind -= (ind&-ind)) {\n            sum += BIT2[ind];\n        }\n        return sum;\n    }\n\n    vector<int> resultArray(vector<int>& nums) {\n        unordered_map<int, int> mapper;\n\n        set<int> s(nums.begin(), nums.end());\n\n        // Compress the range, this is done knowing that there are 10^5 elements and so they can be mapped in this range\n        int curInd = 1;\n        for (auto it: s) {\n            mapper[it] = curInd ++;\n        }\n        N = s.size() + 1;\n        \n        BIT1.resize(N, 0);\n        BIT2.resize(N, 0);\n        vector<int> arr1, arr2;\n\n        // Init the BIT, we keep separate BIT for arr1 and arr2. Add first two elements to arr1 and arr2 respectively\n        update1(mapper[nums[0]], 1);\n        arr1.push_back(nums[0]);\n        update2(mapper[nums[1]], 1);\n        arr2.push_back(nums[1]);\n\n        for (int i = 2; i < nums.size(); i++) {\n            int ind = mapper[nums[i]];\n            \n            // Query the BIT to find the count of elements greated than nums[i] in both arr1 and arr2\n            int greaterCtr1 = query1(N - 1) - query1(ind);\n            int greaterCtr2 = query2(N - 1) - query2(ind);\n\n            if (greaterCtr1 > greaterCtr2) {\n                arr1.push_back(nums[i]);\n                update1(ind, 1);\n            } else if (greaterCtr1 < greaterCtr2) {\n                arr2.push_back(nums[i]);\n                update2(ind, 1);\n            } else if (arr1.size() < arr2.size()) {\n                arr1.push_back(nums[i]);\n                update1(ind, 1);\n            } else if (arr1.size() > arr2.size()) {\n                arr2.push_back(nums[i]);\n                update2(ind, 1);\n            } else {\n                arr1.push_back(nums[i]);\n                update1(ind, 1);\n            }\n        }\n\n        vector<int> ans;\n        for (auto it: arr1) {\n            ans.push_back(it);\n        }\n        for (auto it: arr2) {\n            ans.push_back(it);\n        }\n\n        return ans;\n    }\n};\n```
['C++']