[C++ / Go] - Binary Indexex Tree / BIT - O(nlogn) solution
Intuition\nThe problem needs dynamic data updating and querying so Binary Indexed Tree can be used here\n- We need to compress the value for tree storing.\n\n# 
# Intuition\nThe problem needs dynamic data updating and querying so Binary Indexed Tree can be used here\n- We need to compress the value for tree storing.\n\n# Approach\n- Compress value $10^9$ to maximum of n ($10^5$)\n- Build two BITs to store the occurrences of appeared number in each arrays\n\n# Code\n```C++ []\nclass BIT {\nprivate:\n    vector<int> tree;\n    int n;\n\npublic:\n    BIT(int size) : tree(size + 1), n(size) {}\n\n    void update(int idx, int val) {\n        idx++;\n        while (idx <= n) {\n            tree[idx] += val;\n            idx += idx & -idx;\n        }\n    }\n\n    int query(int idx) {\n        idx++;\n        int result = 0;\n        while (idx > 0) {\n            result += tree[idx];\n            idx -= idx & -idx;\n        }\n        return result;\n    }\n};\n\nclass Solution {\npublic:\n    vector<int> compress(const vector<int>& nums) {\n        vector<int> d(nums.begin(), nums.end());\n        sort(d.begin(), d.end());\n        d.erase(unique(d.begin(), d.end()), d.end());\n        return d;\n    }\n    \n    vector<int> resultArray(vector<int>& nums) {\n        int n = nums.size();\n        \n        vector<int> d = compress(nums);\n        int m = d.size();\n        unordered_map<int, int> trans;\n        for (int i = 0; i < d.size(); i++)\n            trans[d[i]] = i;\n        \n        vector<int> arr1, arr2;\n        BIT bit1(m), bit2(m);\n\n        arr1.push_back(nums[0]);\n        bit1.update(trans[nums[0]], 1);\n\n        arr2.push_back(nums[1]);\n        bit2.update(trans[nums[1]], 1);\n        \n        for (int i = 2; i < n; ++i) {\n            int count1 = arr1.size() - bit1.query(trans[nums[i]]);\n            int count2 = arr2.size() - bit2.query(trans[nums[i]]);\n\n            if (count1 > count2 || (count1 == count2 && arr1.size() <= arr2.size())) {\n                arr1.push_back(nums[i]);\n                bit1.update(trans[nums[i]], 1);\n            } else {\n                arr2.push_back(nums[i]);\n                bit2.update(trans[nums[i]], 1);\n            }\n        }\n\n        arr1.insert(arr1.end(), arr2.begin(), arr2.end());\n        return arr1;\n    }\n};\n```\n```Go []\ntype BIT struct {\n\ttree []int\n\tn    int\n}\n\nfunc newBIT(n int) BIT {\n\treturn BIT {\n\t\ttree: make([]int, n + 1),\n\t\tn:    n,\n\t}\n}\n\nfunc (b *BIT) update(idx, val int) {\n\tidx++\n\tfor idx <= b.n {\n\t\tb.tree[idx] += val\n\t\tidx += idx & -idx\n\t}\n}\n\nfunc (b *BIT) query(idx int) int {\n\tidx++\n\tresult := 0\n\tfor idx > 0 {\n\t\tresult += b.tree[idx]\n\t\tidx -= idx & -idx\n\t}\n\treturn result\n}\n\nfunc compress(nums []int) []int {\n\td := make([]int, len(nums))\n\tcopy(d, nums)\n\n\tsort.Ints(d)\n\tcur := 0\n\tfor i := 1; i < len(d); i++ {\n\t\tif d[i] != d[cur] {\n\t\t\tcur++\n\t\t\td[cur] = d[i]\n\t\t}\n\t}\n\treturn d[:cur + 1]\n}\n\nfunc resultArray(nums []int) []int {\n    n := len(nums)\n\n\td := compress(nums)\n    m := len(d)\n\ttrans := make(map[int]int)\n\tfor i, val := range d {\n\t\ttrans[val] = i\n\t}\n\n\tvar arr1, arr2 []int\n\tbit1 := newBIT(m)\n\tbit2 := newBIT(m)\n\n    arr1 = append(arr1, nums[0])\n    bit1.update(trans[nums[0]], 1)\n\n    arr2 = append(arr2, nums[1])\n    bit2.update(trans[nums[1]], 1)\n\n    for i := 2; i < n; i++ {\n\t\tcount1 := len(arr1) - bit1.query(trans[nums[i]])\n\t\tcount2 := len(arr2) - bit2.query(trans[nums[i]])\n\n\t\tif count1 > count2 || (count1 == count2 && len(arr1) <= len(arr2)) {\n\t\t\tarr1 = append(arr1, nums[i])\n\t\t\tbit1.update(trans[nums[i]], 1)\n\t\t} else {\n\t\t\tarr2 = append(arr2, nums[i])\n\t\t\tbit2.update(trans[nums[i]], 1)\n\t\t}\n\t}\n\n\tarr1 = append(arr1, arr2...)\n\treturn arr1\n}\n```\n\n# Complexity\n- Time complexity: $O(nlogn)$\n    - Average time complexity for BIT operation : $O(logn)$\n    - Loop through n numbers => $O(nlogn)$\n- Space complexity: $O(n)$ for storing the tree structure\n\n
['Binary Indexed Tree', 'C++', 'Go']