[Python] Fenwick tree O(NlogN) solution beats 99%
This solution is adapted from a similar C++ solution. Here\'s the basic idea:\n- fw and bw are two Fenwick trees.\n- fw.sum(i+1) returns the number of ratings l
This solution is adapted from a similar [C++ solution](https://leetcode.com/problems/count-number-of-teams/discuss/555196/C%2B%2B-solutions-O(n-3)-O(n-2)-and-O(nlogn)). Here\'s the basic idea:\n- `fw` and `bw` are two Fenwick trees.\n- `fw.sum(i+1)` returns the number of ratings less than `rating[i]` before `rating[i]`.\n- `bw.sum(N-i)` returns the number of ratings greater than `rating[i]` after `rating[i]`.\n- Iterate `ratings` and use every rating as the center pivot, then the number of increasing 3-tuples with pivot `ratings[i]` is simply `fw.sum(i+1) * bw.sum(N-i)`.\n- Similarly, the number of decreasing 3-tuples can be deduced from `fw.sum(i+1)` and `bw.sum(N-i)` since every rating is unique.\n```python\nclass FenwickTree:              # a.k.a. Binary Index Tree (BIT)\n    def __init__(self, N: int):\n        self.N = N\n        self.arr = [0] * N\n        \n    def sum(self, i: int):      # i is 1-indexed\n        s = 0\n        while i:\n            s += self.arr[i-1]\n            i -= i & -i\n        return s\n    \n    def add(self, i: int, k):   # i is 1-indexed\n        while i <= self.N:\n            self.arr[i-1] += k\n            i += i & -i\n            \n\nclass Solution:\n    def numTeams(self, rating: List[int]) -> int:\n        N = len(rating)\n        fw = FenwickTree(N)\n        bw = FenwickTree(N)\n        \n        r = sorted((n, i) for i, n in enumerate(rating))\n        for n, i in reversed(r):\n            bw.add(N-i, 1)\n        \n        ans = 0\n        for n, i in r:\n            bw.add(N-i, -1)\n            a, b = fw.sum(i+1), bw.sum(N-i)\n            ans += a * b + (i - a) * (N - i - b - 1)\n            fw.add(i+1, 1)\n        return ans\n```\nVote up if you think it\'s helpful, thanks!
['Binary Tree', 'Python']