Binary Indexed Tree
Complexity\n- Time complexity: O(n \log n)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O(n)\n Add your space complexity here, e.g. O(n) \
# Complexity\n- Time complexity: $$O(n \\log n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nstruct FenwickTree {\n    vector<int> tree;\n    FenwickTree(int n) : tree(n) {}\n    int prefix_sum(int pos) {\n        int ans = 0;\n        for (++pos; pos > 0; pos -= pos & -pos) {\n            ans += tree[pos-1];\n        }\n        return ans;\n    } \n    void add(int pos, int v) {\n        for (++pos; pos <= tree.size(); pos += pos & -pos) {\n            tree[pos-1] += v;\n        }\n    }\n};\n\nclass Solution {\npublic:\n    vector<int> resultArray(vector<int>& nums) {\n        auto ord = nums;\n        sort(begin(ord), end(ord));\n        ord.erase(unique(ord.begin(), ord.end()), ord.end());\n\n        vector<int> arr1, arr2;\n        FenwickTree tree1(ord.size()), tree2(ord.size());\n\n        arr1.emplace_back(nums[0]);\n        arr2.emplace_back(nums[1]);\n        tree1.add(lower_bound(begin(ord), end(ord), nums[0])-begin(ord), +1);\n        tree2.add(lower_bound(begin(ord), end(ord), nums[1])-begin(ord), +1);\n\n        for (int i = 2; i < nums.size(); ++i) {\n            int pos = lower_bound(begin(ord), end(ord), nums[i]) - begin(ord);\n            int in1 = arr1.size() - tree1.prefix_sum(pos);\n            int in2 = arr2.size() - tree2.prefix_sum(pos);\n\n            bool add_to2 = (in2 > in1) || (in1 == in2 && arr2.size() < arr1.size());\n            if (add_to2) {\n                arr2.emplace_back(nums[i]);\n                tree2.add(pos, +1);\n            } else {\n                arr1.emplace_back(nums[i]);\n                tree1.add(pos, +1);\n            }\n        }\n\n        for (int x : arr2) arr1.emplace_back(x);\n        return arr1;\n    }\n};\n```
['Binary Indexed Tree', 'C++']