跟着姚桑学算法-数组中的逆序对

题. 数组中的逆序对

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

输入一个数组，求出这个数组中的逆序对的总数。

数据范围
给定数组的长度 [0,100]。

样例

输入：[1,2,3,4,5,6,0]

输出：6

【题解】--- 树状数组

用树状数组维护一个数字个数的序列；数据离线，逆向查询。
在每次查询一个数前，在树状数组里查询小于这个数的个数，也就是查询个数后面的逆序对的个数；
最后把这个数加一即可。

提到 树状数组 ，树状数组是一个查询和修改复杂度都为log(n)的数据结构。主要用于数组的单点修改&&区间求和.

另外一个拥有类似功能的是线段树。

具体区别和联系如下：

1. 两者在复杂度上同级, 但是树状数组的常数明显优于线段树, 其编程复杂度也远小于线段树.
2. 树状数组的作用被线段树完全涵盖, 凡是可以使用树状数组解决的问题, 使用线段树一定可以解决, 但是线段树能够解决的问题树状数组未必能够解决.
3. 树状数组的突出特点是其编程的极端简洁性, 使用lowbit技术可以在很短的几步操作中完成树状数组的核心操作，其代码效率远高于线段树。

复杂度分析：

时间复杂度为O(NlogN)。

C++代码实现：

class Solution {
public:
    int cnt,n,c[1000000],ans;
    void add(int x){for(; x <= cnt; x += x & -x) c[x] ++;}
    int ask(int x)
    {
        int res = 0;
        for(; x; x -= x & -x) res += c[x];
        return res;
    }
    int inversePairs(vector<int>& nums) {
        set<int> st;
        unordered_map<int,int> ump;
        cnt = 0; ans = 0; n = nums.size();
        memset(c, 0, sizeof c);
        for(auto &i : nums) st.insert(i);
        for(auto it = st.begin(); it != st.end(); it++ ) ump[*it] = ++cnt;
        for(int i = nums.size() - 1; i >= 0; i--) ans += ask(ump[nums[i]] - 1), add(ump[nums[i]]);
        return ans;
    }
};