Binary indexed tree with ranks
Intuition\nThe code below uses a binary indexed tree (BIT) to store the ranks of the elements in arr1 and arr2. Then it is possible to get the greaterCount valu
# Intuition\nThe code below uses a binary indexed tree (BIT) to store the ranks of the elements in `arr1` and `arr2`. Then it is possible to get the `greaterCount` value in logarithmic time. \n\n# Complexity\n- Time complexity: $$O(n\\log(n))$$\n  Sorting and BIT manipulations.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$.\n  For ranks, bit1, bit2, arr1, arr2.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass BIT:\n    def __init__(self, n):\n        self.values = [0]*(n+1)\n    \n    def add(self, idx):\n        idx += 1\n        values = self.values\n        while idx > 0:\n            values[idx] += 1\n            idx -= idx & (-idx)\n     \n    def greater_count(self, idx):\n        idx += 2\n        values = self.values\n        n = len(values)\n        count = 0\n        while idx < n:\n            count += values[idx]\n            idx += idx & (-idx)\n        return count\n\n    def __str__(self):\n        counts = [self.greater_count(i) for i in range(len(self.values))]\n        return f"{type(self).__name__}({counts})"\n\n\nclass Solution:\n    def resultArray(self, nums: List[int]) -> List[int]:\n        n = len(nums)\n        ranks = [0]*n\n        for r, i in enumerate(sorted(range(n), key=lambda i: nums[i])): \n            ranks[i] = r\n        \n        bit1 = BIT(n)\n        bit2 = BIT(n)\n        arr1 = []\n        arr2 = []\n\n        it = zip(nums, ranks)\n        a, r = next(it)\n        arr1.append(a)\n        bit1.add(r)\n        a, r = next(it)\n        arr2.append(a)\n        bit2.add(r)\n        \n        for a, r in it:\n            c1 = bit1.greater_count(r)\n            c2 = bit2.greater_count(r)\n            if (c1, -len(arr1)) >= (c2, -len(arr2)):\n                arr1.append(a)\n                bit1.add(r)\n            else:\n                arr2.append(a)\n                bit2.add(r)\n\n        del bit1, bit2, ranks\n        arr1.extend(arr2)\n        return arr1\n\n```
['Python3']