FENWICK TREE || C++ || SIMPLEST || FASTEST
\n#include <bits/stdc++.h>\nusing namespace std;\ntypedef long long ll;\ntypedef pair<ll, ll> pi;\n#define forn(i, n) for(int i = 0;i < n;i++)\n#define forn2(i,
```\n#include <bits/stdc++.h>\nusing namespace std;\ntypedef long long ll;\ntypedef pair<ll, ll> pi;\n#define forn(i, n) for(int i = 0;i < n;i++)\n#define forn2(i, s, e) for(int i = s;i < e;i++)\n#define pb push_back\ntypedef vector<int> vi;\ntypedef vector<vi> vvi;\ntypedef vector<ll> vl;\ntypedef pair<double, double> pd;\ntypedef vector<vector<ll>> vvl;\ntypedef vector<bool> vb;\ntypedef vector<string> vs;\ntypedef pair<int, pi>ppi;\ntypedef pair<string, int>p2;\ntypedef pair<pi, int>ps;\nint mod = 1e9 + 7;\ntemplate<typename T>\n \n\nvoid printvec(T& data){\n    for(auto it: data){\n        cout << it << " ";\n    }\n    cout << endl;\n}\n\ntemplate<typename X>\nvoid printpair(X& data){\n    for(auto it: data){\n        cout << it[0] << " " << it[1] << " #### " << endl;\n    }\n}\n\n\nclass fenwickTree{\npublic:\n    vector<int>tree;\n    int cnt;\n    fenwickTree(int n){\n        tree.clear();\n        tree.resize(n+1);\n        cnt = 0;\n    }\n    int sum(int idx){\n        int output = 0;\n        while(idx > 0){\n            output += tree[idx];\n            idx -= idx & (-idx);\n        }\n        return output;\n    }\n    \n    void insert(int idx){\n        cnt++;\n        while(idx <= tree.size()-1){\n            tree[idx]++;\n            idx += idx & (-idx);\n        }\n    }\n};\n\nclass Solution {\npublic:\n    vector<int> resultArray(vector<int>& nums) {\n        map<int, int>mp;\n        map<int, int>mp2;\n        int start = 1;\n        int n = nums.size();\n        vi temp = nums;\n        sort(temp.begin(), temp.end());\n        forn(i, n){\n            mp[temp[i]] = start;\n            mp2[start] = temp[i];\n            start++;\n        }\n        forn(i, n) nums[i] = mp[nums[i]];\n        vi nums1;\n        vi nums2;\n        vi output;\n        fenwickTree *first = new fenwickTree(n);\n        fenwickTree* second = new fenwickTree(n);\n        first -> insert(nums[0]);\n        second -> insert(nums[1]);\n        nums1.pb(nums[0]);\n        nums2.pb(nums[1]);\n        forn2(i, 2, n){\n            int tmp1 = nums1.size() - first -> sum(nums[i]);\n            int tmp2 = nums2.size() - second -> sum(nums[i]);\n            if(tmp1 > tmp2){\n                nums1.pb(nums[i]);\n                first -> insert(nums[i]);\n            }\n            else if(tmp1 < tmp2){\n                nums2.pb(nums[i]);\n                second -> insert(nums[i]);\n            }\n            else{\n                if(first -> cnt < second -> cnt || first -> cnt == second -> cnt){\n                    nums1.pb(nums[i]);\n                    first -> insert(nums[i]);\n                }\n                else{\n                    nums2.pb(nums[i]);\n                    second -> insert(nums[i]);\n                }\n            }\n        }\n        for(auto it: nums1) output.pb(mp2[it]);\n        for(auto it: nums2) output.pb(mp2[it]);\n        return output;\n    }\n};\n```
['Tree', 'C']