Fenwick Tree CPP
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class FenwickTree {
    vector<int> v;
    int counter = 0;
    vector<int> collector;
    
public:
    FenwickTree(int size) {
        v = vector<int>(size + 1, 0);
    }

    void update(int index, int real, int value = 1) {
        while (index < v.size()) {
            v[index] += value;
            index += (index & -index);
        }
        counter++;
        collector.push_back(real);
    }

    int find_sum(int index) {
        int sum = 0;
        while (index > 0) {
            sum += v[index];
            index -= (index & -index); 
        }
        return sum;
    }

    int query(int index) {
        return find_sum(v.size()-1) - find_sum(index);
    }

    int count() {
        return counter;
    }

    vector<int> collected_elements() {
        return collector;
    }
};

class Solution {
public:
    vector<int> resultArray(vector<int>& nums) {
        int count = 0; 
        unordered_map<int, int> m;
        vector<int> nums_copy = nums;
        sort(nums_copy.begin(), nums_copy.end());
        for(int i=0; i< nums_copy.size(); i++) {
            m[nums_copy[i]] = i + 1;
        }
        FenwickTree * tree1 = new FenwickTree(nums.size());
        FenwickTree * tree2 = new FenwickTree(nums.size());

        tree1 -> update(m[nums[0]], nums[0]);
        tree2 -> update(m[nums[1]], nums[1]);

        for(int i=2; i<nums.size(); i++) {
            int sz1 = tree1->query(m[nums[i]]);
            int sz2 = tree2 -> query(m[nums[i]]);
            if (sz1 == sz2) {
                if (tree2->count() < tree1->count()) {
                    tree2->update(m[nums[i]], nums[i]);
                } else {
                    tree1->update(m[nums[i]], nums[i]);
                }
            } else if (sz1 > sz2) {
                tree1->update(m[nums[i]], nums[i]);
            } else {
                tree2->update(m[nums[i]], nums[i]);
            }
        }
        vector<int> ans;
        vector<int> arr = tree1->collected_elements();
        for(auto i: arr) {
            ans.push_back(i);
        }
        arr = tree2->collected_elements();
        for(auto i: arr) {
            ans.push_back(i);
        }
        return ans;
    }
};

```
['C++']