在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
限制：
0 <= 数组长度 <= 50000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
树状数组，由于含有负值且绝对值可能很大，但是总个数有限制，需要先离散化，把原值换为大小位置再用树状数组。
代码：
class Solution { public: int f[50001]; int lowbit(int t) {return t&-t;} void update(int x) { while(x <= 50000) { f[x] ++; x += lowbit(x); } } int get(int x) { int sum = 0; while(x > 0) { sum += f[x]; x -= lowbit(x); } return sum; } int reversePairs(vector<int>& nums) { int ans = 0; vector<int> temp = nums; sort(temp.begin(),temp.end()); for(int i = 0;i < nums.size();i ++) { nums[i] = lower_bound(temp.begin(),temp.end(),nums[i]) - temp.begin() + 1; update(nums[i]); ans += i + 1 - get(nums[i]); } return ans; } };
原文：https://www.cnblogs.com/8023spz/p/13737613.html