Fenwick tree without ID
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```\n\nclass FenwickTree{\npublic:\n    int N;\n    unordered_map<int,int> tree;\n\n    FenwickTree(int n){\n        N = n;\n    }\n\n    int lsb(int val){\n        return val & -val;\n    }\n\n    int prefixSum(int pos){\n        int sum = 0;\n        while(pos){\n            sum += tree[pos];\n            pos &= ~lsb(pos);\n        }\n        return sum;\n    }\n\n    int sumRange(int start, int end){\n        return prefixSum(end)-prefixSum(start-1);\n    }\n\n    void update(int pos, int val){\n        while(pos <= N){\n            tree[pos] += val;\n            pos += lsb(pos);\n        }\n    }\n};\n\nclass Solution {\npublic:\n    vector<int> resultArray(vector<int>& nums) {\n        vector<int> arr1, arr2;\n        \n        int mx = 0;\n        for(int i : nums) \n            mx = max(i, mx);\n        \n        FenwickTree f1(mx+1), f2(mx+1);\n        \n        for(int j = 0; j<nums.size(); j++){\n            int i = nums[j];\n            \n            if(j == 0){\n                arr1.push_back(i);\n                f1.update(i, 1);\n                continue;\n            }else if(j == 1){\n                arr2.push_back(i);\n                f2.update(i, 1);\n                continue;\n            }\n            \n            \n            int ctr1 = f1.sumRange(i+1, mx);\n            int ctr2 = f2.sumRange(i+1, mx);\n            \n            \n            if(ctr1 > ctr2){\n                arr1.push_back(i);\n                f1.update(i, 1);\n            }else if(ctr2 > ctr1){\n                arr2.push_back(i);\n                f2.update(i, 1);\n            }else if(arr1.size() > arr2.size()){\n                arr2.push_back(i);\n                f2.update(i, 1);\n            }else{\n                arr1.push_back(i);\n                f1.update(i, 1);\n            }\n        }\n        \n        for(int i :arr2) \n            arr1.push_back(i);\n        return arr1;\n    }\n};\n```
['C++']