剑指 Offer 51. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 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;
    }
};