Fenwick Tree Implementation
\n\n# Code\n\nclass Solution {\npublic:\n\n    struct fenwick {\n        vector <int> bit;\n        int n;\n\n        fenwick(int _n) {\n            n = _n;\n  
\n\n# Code\n```\nclass Solution {\npublic:\n\n    struct fenwick {\n        vector <int> bit;\n        int n;\n\n        fenwick(int _n) {\n            n = _n;\n            bit.resize(n + 5, 0);\n        }\n\n        void upd(int idx) {\n            while (idx) {\n                bit[idx] ++;\n                idx -= idx & -idx;\n            }\n        }\n\n        int get(int idx, int ans = 0) {\n            while (idx <= n) {\n                ans += bit[idx];\n                idx += idx & -idx;\n            } return ans;\n        }\n    };\n\n    vector<int> resultArray(vector<int>& nums) {\n        vector <int> cmp = nums;\n        sort(cmp.begin(), cmp.end());\n        cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());\n\n        auto get = [&] (int x) {\n            return lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin() + 1;\n        };\n\n        int distinct = cmp.size();\n\n        fenwick fenA(distinct), fenB(distinct);\n\n        vector <int> a, b;\n\n        fenA.upd(get(nums[0]));\n        fenB.upd(get(nums[1]));\n        a.push_back(nums[0]);\n        b.push_back(nums[1]);\n        \n        for (int i = 2; i < nums.size(); i ++) {\n            int x = nums[i];\n            int id = get(x);\n            int cntA = fenA.get(id + 1);\n            int cntB = fenB.get(id + 1);\n\n            if (cntA == cntB) {\n                if (a.size() <= b.size()) {\n                    a.push_back(x);\n                    fenA.upd(id);\n                } else {\n                    b.push_back(x);\n                    fenB.upd(id);\n                }\n                continue;\n            }\n\n            if (cntA > cntB) {\n                a.push_back(x);\n                fenA.upd(id);\n            } else {\n                b.push_back(x);\n                fenB.upd(id);\n            }\n        }\n\n        for (int x: b)\n            a.push_back(x);\n\n        return a;\n    }\n};\n```
['C++']