题解 | 数组中的逆序对 wok总算做出来了 看注释

#include <algorithm>
#include <vector>
class BIT{
    int n;
    vector<int> tree;
    public:
    BIT(int m):n(m),tree(m+1){};
    int query(int index){
        int sum=0;
        while(index>0){
            sum+=tree[index];
            index-=lowbit(index);
        }
        return sum;

    }
    int lowbit(int index){
        return index&-index;
    }
    //更新数组
    void update(int index){
        while(index<=n){
            tree[index]++;
            index+=lowbit(index);
        }
    }
    
};
class Solution{
    public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int InversePairs(vector<int>& nums) 
{
        // write code here
        //——————————————————没思路
        //看了解析后懂了 一种是分治的解法 用归并进行排序 一旦有右>左 说明有逆序
        //一种是求这个数组 前面比它大的数的个数 暴力解法n2 但有种优化的方法 使用元素值对应新数组下标 每遍历一个元素 记录它前面已存在的元素个数 用下标来访问 再加和。但这基本上也达到了on的数量级。还有一个问题 数字的值非常大 如果按照值对应下标的策略 则数组也非常大 可能会超出内存限制 。优化一 不就是求前缀吗 可以用树状数组 边更新元素边求前缀和。这是树状数组擅长的。优化二 用离散化的方法将数组的值映射到一个可接受的范围。
        /*
        int size=nums.size();
        vector<int> tmp(size);
        sort(nums.begin(), nums.end());
        tmp[0]=1;//树状数组下标从1开始
        int cnt=1;
        for(int i=1;i<size-1;i++){
            if(nums[i]==nums[i-1]){
                tmp[i]=cnt;
            }
            //cnt++;
            tmp[i]=++cnt;
        }
        */
        //tmp数组 怎么让这个排序了的、离散化了的数组再回到原来的顺序 两个不够 似乎还要再来一个数组记录原来的位置关系。
        //但有一个时间换空间的方法 
         int size=nums.size();
        vector<int> tmp=nums;
        sort(tmp.begin(), tmp.end());
        //tmp[0]=1;//树状数组下标从1开始 保证树状数组的下标不会用0；只会从1开始
        for(int i=0;i<size;i++){
            nums[i]=lower_bound(tmp.begin(), tmp.end(), nums[i])-tmp.begin()+1;//注意这句 很细节 迭代器返回迭代器类型 不是int 差得到的是距离。
        }
        BIT mytree(size);
        int p=0;
        for(int i=0;i<size;i++){
            /*
             mytree.update(nums[i]);
            p=(p+mytree.query(size)-mytree.query(i)-1)%1000000007;
            */
            mytree.update(nums[i]);
            p=(p+mytree.query(size)-mytree.query(nums[i]))%1000000007;
            
            
           
        }
        return p;
        }
    };