Segment tree | C++
Intuition\nThe complexity of function "greaterCount" is the most important thing. We need a sorted container which take a short time to insert and count the gre
# Intuition\nThe complexity of function "greaterCount" is the most important thing. We need a sorted container which take a short time to insert and count the greater elements.\n\nFollowing table is time complexity of two built-in containers in c++. Both of them are not sufficient:\n\n| container | insertion complexity | greaterCount complexity|\n|-----------|----------------------|------------------------|\n| vector\t| o(n)                 | o(log(n))              |\n| multiset\t| o(log(n))            | o(n)                   |\n\nSegment tree is a good choice because the inserting complexity and finding complexity are all o(log(n)). Just a small modification in segment tree, we count the values in a tree rather than find the sum of values in a tree.\n\n# Approach: Segment tree\n\n1. We need two arrays arr1, arr2 to push numbers. Each array has a segment tree to count the values in that array.\n2. Push the nums[0] to arr1, and nums[1] to arr2. Of course, insert them to the associated segment tree. \n3. Iterate through remaining numbers\n3.1. Check conditions mentioned in the problems by using the functions provided by segment trees and arrays. Insert that number to arr1 or arr2 based on the conditions.\n4. Concatenate arr1 and arr2\n\n## Segment tree\nIn this section, I visualize some operations in a segment tree. The following steps will be visualized:\n1. Create a segment tree for data in range [1, 4]. A node in segment tree has a range and a count variable.\n![image.png](https://assets.leetcode.com/users/images/3e9fdfb5-d9c1-4f8c-8e5c-feb27b6eb1e1_1709449997.4256709.png)\n\n2. Insert 3 to segment tree\n![image.png](https://assets.leetcode.com/users/images/7cf12d33-ee7d-4703-914d-05a0a78fae04_1709450221.2104793.png)\n\n3. Insert 1 to segment tree\n![image.png](https://assets.leetcode.com/users/images/c56b52e7-a5bb-4217-8300-8954b4289d28_1709450251.562231.png)\n\n4. Insert 4 to segment tree\n![image.png](https://assets.leetcode.com/users/images/e7d5d975-8dcd-4df2-8a3f-82e462add4ee_1709450289.0261335.png)\n\n5. Count numbers which is greater than 2\n![image.png](https://assets.leetcode.com/users/images/4be2b15d-99a4-4539-aec3-33dff93a34dc_1709450321.8454144.png)\n\n# Complexity\n- Time complexity:\no(n*log(m))\nwhere n is the sum of size of two arrays, m is the maximum value (10e9)\n\n- Space complexity:\no(m)\nwhere m is the maximum value (10e9)\n\n# Code\n```\nclass Segment\n{\npublic:\n    int mMin;\n    int mMax;\n    int count;\n    Segment* mLeftHalf;\n    Segment* mRightHalf;\n    \n    Segment(int min_, int max_) : mMin(min_), mMax(max_), count(0), mLeftHalf(nullptr), mRightHalf(nullptr)\n    {\n        // Do nothing\n    }\n    \n    void insert(int value)\n    {\n        count++;\n        if (mMin != mMax)\n        {\n            // Add value to sub-segments\n            int leftMiddle = (mMin + mMax) / 2;\n            if (value <= leftMiddle)\n            {\n                if (mLeftHalf == nullptr) mLeftHalf = new Segment(mMin, leftMiddle);\n                mLeftHalf->insert(value);\n            }\n            else\n            {\n                if (mRightHalf == nullptr) mRightHalf = new Segment(leftMiddle + 1, mMax);\n                mRightHalf->insert(value);\n            }\n        }\n    }\n    \n    int greaterCount(int value)\n    {\n        // Leave segment\n        if (mMin == mMax) return int(value < mMin);\n\n        int leftMiddle = (mMin + mMax) / 2;\n        int ans = 0;\n        // Left half\n        if (value < mMin)\n            ans += mLeftHalf != nullptr ? mLeftHalf->count : 0;\n        else if (value < leftMiddle)\n            ans += mLeftHalf != nullptr ? mLeftHalf->greaterCount(value) : 0;\n        // Right half\n        if (value <= leftMiddle)\n            ans += mRightHalf != nullptr ? mRightHalf->count : 0;\n        else\n            ans += mRightHalf != nullptr ? mRightHalf->greaterCount(value) : 0;\n        return ans;\n    }\n};\n\nclass Solution {\npublic:\n    vector<int> resultArray(vector<int>& nums) {\n        int minValue = *min_element(nums.begin(), nums.end());\n        int maxValue = *max_element(nums.begin(), nums.end());\n        Segment seg1(minValue, maxValue);\n        Segment seg2(minValue, maxValue);\n        vector<int> arr1 = {nums[0]};\n        vector<int> arr2 = {nums[1]};\n        seg1.insert(nums[0]);\n        seg2.insert(nums[1]);\n        \n        for (int i = 2; i < nums.size(); i++)\n        {\n            int gt1 = seg1.greaterCount(nums[i]);\n            int gt2 = seg2.greaterCount(nums[i]);           \n            if (gt1 > gt2)\n            {\n                arr1.push_back(nums[i]);\n                seg1.insert(nums[i]);\n            }\n            else if (gt1 < gt2)\n            {\n                arr2.push_back(nums[i]);\n                seg2.insert(nums[i]);\n            }\n            else\n            {\n                if (arr1.size() > arr2.size())\n                {\n                    arr2.push_back(nums[i]);\n                    seg2.insert(nums[i]);\n                }\n                else\n                {\n                    arr1.push_back(nums[i]);\n                    seg1.insert(nums[i]); \n                }\n            }\n        }\n        arr1.insert(arr1.end(), arr2.begin(), arr2.end());\n        return arr1;\n    }\n};\n```
['C++']