[Python3] Fenwick Tree solution, O(n log(n)) (100%)
This is a solution based on the one from this post: https://leetcode.com/problems/count-number-of-teams/discuss/554907/Java-Detailed-Explanation-TreeSet-greater
This is a solution based on the one from this post: https://leetcode.com/problems/count-number-of-teams/discuss/554907/Java-Detailed-Explanation-TreeSet-greater-BIT-(Fenwick-Tree)-O(NlogN)\n\nI thought that this was a very interesting and efficient approach, but still wanted to improve upon it by reducing the size of the Fenwick Trees. The main idea is to build the Fenwick Tree on the "rank" of the ratings, i.e. the index of the ratings when sorted, which reduces the size of the Fenwick Tree from `N = 10^5`, the largest possible input, to `n`, the length of the array. Here\'s my Python solution.\n\nI reached 44ms (99.53%) with it.\n\n```\nclass BIT:\n\t"""A Binary Index Tree, a.k.a. Fenwick Tree."""\n    \n    def __init__(self, n: int):\n        self.n = n\n        self.bits = [0] * (n + 1)\n        self.total = 0\n\t\t# Total stores the total sum of the tree. This makes retrieving right sums more efficient.\n    \n    def update(self, index: int, value: int):\n\t\t"""Add value `value` at index `index`: O(log(n))."""\n        index += 1\n        self.total += value\n        while index <= self.n:\n            self.bits[index] += value\n            index += index & (-index)\n    \n    def getsum(self, index: int):\n\t\t"""Get the sum of values to the left of `index` if positive, or to the right if negative; O(log(n))."""\n        if index < 0:\n\t\t\t# `~index == - index - 1`.\n\t\t\t# `bit.getsum(~index)` will retrieve the sum of values from `index + 1` to `n`.\n            return self.total - self.getsum(~index)\n        if index >= self.n:\n            return self.total\n        ans = 0\n        index += 1\n        while index > 0:\n            ans += self.bits[index]\n            index -= index & (-index)\n        return ans\n\n\nclass Solution:\n\n    def numTeams(self, rating: List[int]) -> int:\n        n = len(rating)\n        mapping = {r: i for i, r in enumerate(sorted(rating))}\n        left_counts = BIT(n)\n        right_counts = BIT(n)\n        for r in rating[1:]:\n            right_counts.update(mapping[r], 1)\n        ans = 0\n        left_counts.update(mapping[rating[0]], 1)\n        for r in rating[1 : -1]:\n            index = mapping[r]\n            right_counts.update(index, -1)\n            ans += left_counts.getsum(index) * right_counts.getsum(~index)\n            ans += left_counts.getsum(~index) * right_counts.getsum(index)\n            left_counts.update(index, 1)\n        return ans\n```\n\nAn alternative solution, which is slightly more efficient (only two calls to `getsum` per loop, as opposed to four). I reached 36ms (100%) with it:\n\n```\nclass BIT:\n    """A Binary Index Tree, a.k.a. Fenwick Tree."""\n    \n    def __init__(self, n: int):\n        self.n = n\n        self.bits = [0] * (n + 1)\n        self.total = 0\n\t\t# Total stores the total sum of the tree. This makes retrieving right sums more efficient.\n    \n    def update(self, index: int, value: int):\n        """Add value `value` at index `index`: O(log(n))."""\n        index += 1\n        self.total += value\n        while index <= self.n:\n            self.bits[index] += value\n            index += index & (-index)\n    \n    def getsum(self, index: int):\n        """Get the sum of values to the left of `index`; O(log(n))."""\n        ans = 0\n        index += 1\n        while index > 0:\n            ans += self.bits[index]\n            index -= index & (-index)\n        return ans\n\n\nclass Solution:\n\n    def numTeams(self, rating: List[int]) -> int:\n        n = len(rating)\n        mapping = {r: i for i, r in enumerate(sorted(rating))}\n        left_counts = BIT(n)\n        right_counts = BIT(n)\n        for r in rating[1:]:\n            right_counts.update(mapping[r], 1)\n        ans = 0\n        left_counts.update(mapping[rating[0]], 1)\n        for r in rating[1 : -1]:\n            index = mapping[r]\n            right_counts.update(index, -1)\n            left_sum = left_counts.getsum(index)\n            right_sum = right_counts.getsum(index)\n            ans += left_sum * (right_counts.total - right_sum)\n            ans += right_sum * (left_counts.total - left_sum)\n            left_counts.update(index, 1)\n        return ans\n```
[]