剑指 Offer 51. 数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4] 输出: 5
限制：
0 <= 数组长度 <= 50000树状数组
思路
相较于 315. 计算右侧小于当前元素的个数 本题直观一点，代码几乎一样！
题解
class BIT: def __init__(self, n): self.tree = [0] * (n+1) def add(self, idx, val): i = idx + 1 while i < len(self.tree): self.tree[i] += val i += self.lowbit(i) def prefix(self, idx): i = idx + 1 sum_ = 0 while i > 0: sum_ += self.tree[i] i -= self.lowbit(i) return sum_ def lowbit(self, x): return x & (-x) class Solution: def reversePairs(self, nums: List[int]) -> int: if len(nums) == 1: return 0 res = 0 uniques = sorted(list(set(nums))) rank_map = {k:i for i, k in enumerate(uniques)} b = BIT(len(uniques)) for i in range(len(nums)-1, -1, -1): rank = rank_map[nums[i]] res += b.prefix(rank-1) b.add(rank, 1) return res