题解 | #数组中的逆序对#

class BIT{
private: 
    vector<int> tree;
    int m;
public:
    BIT(int n):m(n), tree(n + 1){}
    int lowbit(int x){
        return x & (-x);
    }
    void update(int x){
        while(x <= m){
            tree[x]++;
            x += lowbit(x);
        }
    }
    int query(int x){
        int res = 0;
        while(x){
            res += tree[x];
            x -= lowbit(x);
        }
        return res;
    }

};
class Solution {
public:
    /**
     * @param nums int整型vector 
     * @return int整型
     */
    int serch(vector<int> nums,int target){
        int left = 0;
        int right = nums.size() - 1;
        while(left <= right){
            auto mid = (left + right) / 2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return -1;
    }
    int InversePairs(vector<int>& nums) {
        // write code here|
        vector<int> temp = nums;
        int mod = 1000000007;
        int n = nums.size();
        
        sort(temp.begin(), temp.end());
        for(int i = 0; i < n; ++i){
            nums[i] = serch(temp, nums[i]) + 1;
        }
        BIT bit(n);
        int res = 0;
        for(int i = 0; i < n; ++i){
            res = (res + bit.query(n) - bit.query(nums[i]) )% mod; //查询大于他的一共有多少个数
            bit.update(nums[i]);// 看哪个位置有数
        }
        return res;
    }
};