Very Simple Fenwick Tree Solution || Explained
Prerequisites\n###### Knowledge of Fenwick Tree (i.e. Binary Indexed Tree) is required.\n# Complexity\n- Time complexity: O(n*log(n)) \n\n- Space complexity: O(
# Prerequisites\n###### Knowledge of Fenwick Tree (i.e. Binary Indexed Tree) is required.\n# Complexity\n- Time complexity: $$O(n*log(n))$$ \n\n- Space complexity: $$O(n)$$ \n\n# Code\n```\nclass Solution {\n    vector<int> BIT1, BIT2;\n\n    void update(int i, int delta, int n, vector<int>& BIT)\n    {\n        for(; i<=n; i += (i&-i)) {\n            BIT[i] += delta;\n        }\n    }\n\n    int query(int i, vector<int>& BIT)\n    {\n        int sum = 0;\n        for(; i>0; i -= (i&-i)) {\n            sum += BIT[i];\n        }\n     return sum;\n    }\n    //this is standard method of handling large numbers by compressing them into the range [1,n]\n    vector<int> compressCordinates(vector<int> arr)\n    {\n      int k = 1;\n      map<int,int> m;\n        vector<int> temp = arr;\n        for(auto it : arr) {\n            m[it]++;\n        }\n        for(auto it : m) {\n            m[it.first] = k++;\n        }\n        k = 0;\n        for(auto it : arr) {\n            temp[k++] = m[it];\n        }\n     return temp;\n    }\n    \n    int greaterCount(vector<int>& BIT, int val)\n    {\n        int n = BIT.size()-1; \n        return query(n,BIT) - query(val,BIT); //find count of numbers in the range [val,MAX_SIZE]\n    }\npublic:\n    vector<int> resultArray(vector<int>& arr) {\n        int n = arr.size();\n        vector<int> arr1,arr2,ans;\n        vector<int> nums = compressCordinates(arr); //compress the numbers into the range [1,n]\n        \n        BIT1.resize(n+1);\n        BIT2.resize(n+1);\n        \n        //as stated in the problem\n        arr1.push_back(arr[0]); //push 1st element in arr1\n        update(nums[0],1,n,BIT1);\n        arr2.push_back(arr[1]); //push 2nd element in arr2\n        update(nums[1],1,n,BIT2);\n        \n        //just simulate conditions given in problem statement\n        for(int i=2; i<nums.size(); i++) {\n            if(greaterCount(BIT1, nums[i]) > greaterCount(BIT2, nums[i])) \n            {\n                update(nums[i],1,n,BIT1);\n                arr1.push_back(arr[i]);\n            }\n            else if(greaterCount(BIT1, nums[i]) < greaterCount(BIT2, nums[i])) \n            {\n                update(nums[i],1,n,BIT2);\n                arr2.push_back(arr[i]);\n            }\n            else \n            {\n                 if(arr1.size() <= arr2.size()) \n                {\n                    update(nums[i],1,n,BIT1);\n                    arr1.push_back(arr[i]);\n                }\n                else \n                {\n                    update(nums[i],1,n,BIT2);\n                    arr2.push_back(arr[i]);\n                }\n            }\n        }\n    \n        for(auto it : arr1) { ans.push_back(it); }  \n        for(auto it : arr2) { ans.push_back(it); }\n        \n     return ans;\n    }\n};\n```
['Binary Indexed Tree', 'Simulation', 'C++']