Easy Fenwick tree Solution 🥺
\n\n# Code\n\nclass Solution\n{\npublic:\n\n//GFG Fenwick tree start\n\n    int getSum(int BITree[], int index)\n    {\n        int sum = 0; // Initialize resul
\n\n# Code\n```\nclass Solution\n{\npublic:\n\n//GFG Fenwick tree start\n\n    int getSum(int BITree[], int index)\n    {\n        int sum = 0; // Initialize result\n\n        // index in BITree[] is 1 more than the index in arr[]\n        index = index + 1;\n\n        // Traverse ancestors of BITree[index]\n        while (index > 0)\n        {\n\n            // Add current element of BITree to sum\n            sum += BITree[index];\n\n            // Move index to parent node in getSum View\n            index -= index & (-index);\n        }\n        return sum;\n    }\n\n    // Updates a node in Binary Index Tree (BITree) at given index\n    // in BITree. The given value \'val\' is added to BITree[i] and\n    // all of its ancestors in tree.\n    void updateBIT(int BITree[], int n, int index)\n    {\n\n        // index in BITree[] is 1 more than the index in arr[]\n        index = index + 1;\n\n        // Traverse all ancestors and add \'val\'\n        while (index <= n)\n        {\n\n            // Add \'val\' to current node of BI Tree\n            BITree[index]++;\n\n            // Update index to that of parent in update View\n            index += index & (-index);\n        }\n    }\n\n    // Constructs and returns a Binary Indexed Tree for given\n    // array of size n.\n    int *constructBITree(int n)\n    {\n\n        int *BITree = new int[n + 1];\n        for (int i = 1; i <= n; i++)\n            BITree[i] = 0;\n        return BITree;\n    }\n\n// GFG Fenwick tree ends\n\n    vector<int> resultArray(vector<int> &nums)\n    {\n        vector<int> v1, v2;\n        int ct = 0;\n        vector<int> v = nums;\n        sort(v.begin(), v.end());\n        unordered_map<int, int> mp;\n        for (auto &it : v)\n        {\n            if (mp.find(it) == mp.end())\n            {\n                mp[it] = ct++;\n            }\n        }\n        int *BITree = constructBITree(ct);\n        int *BITree2 = constructBITree(ct);\n        for (auto &it : nums)\n        {\n            if (!v1.size())\n            {\n                v1.push_back(it);\n                updateBIT(BITree, ct, mp[it]);\n            }\n            else if (!v2.size())\n            {\n                v2.push_back(it);\n                updateBIT(BITree2, ct, mp[it]);\n            }\n            else\n            {\n                int a = v1.size() - getSum(BITree, mp[it]);\n                int b = v2.size() - getSum(BITree2, mp[it]);\n                if (a > b)\n                {\n                    v1.push_back(it);\n                    updateBIT(BITree, ct, mp[it]);\n                }\n                else if (b > a)\n                {\n                    v2.push_back(it);\n                    updateBIT(BITree2, ct, mp[it]);\n                }\n                else\n                {\n                    if (v1.size() > v2.size())\n                    {\n                        v2.push_back(it);\n                        updateBIT(BITree2, ct, mp[it]);\n                    }\n                    else\n                    {\n                        v1.push_back(it);\n                        updateBIT(BITree, ct, mp[it]);\n                    }\n                }\n            }\n        }\n        nums.clear();\n        for (auto &it : v1)\n            nums.push_back(it);\n        for (auto &it : v2)\n            nums.push_back(it);\n        return nums;\n    }\n};\n```
['C++']