题. 数组中的逆序对
在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
输入一个数组，求出这个数组中的逆序对的总数。
数据范围
给定数组的长度 [0,100]。
样例
输入：[1,2,3,4,5,6,0]
输出：6
AI 代码解读
【题解】--- 树状数组
用树状数组维护一个数字个数的序列；数据离线，逆向查询。
在每次查询一个数前，在树状数组里查询小于这个数的个数，也就是查询个数后面的逆序对的个数；
最后把这个数加一即可。
提到 树状数组 ，树状数组是一个查询和修改复杂度都为log(n)的数据结构。主要用于数组的单点修改&&区间求和.
另外一个拥有类似功能的是线段树。
具体区别和联系如下：
- 两者在复杂度上同级, 但是树状数组的常数明显优于线段树, 其编程复杂度也远小于线段树.
- 树状数组的作用被线段树完全涵盖, 凡是可以使用树状数组解决的问题, 使用线段树一定可以解决, 但是线段树能够解决的问题树状数组未必能够解决.
- 树状数组的突出特点是其编程的极端简洁性, 使用lowbit技术可以在很短的几步操作中完成树状数组的核心操作，其代码效率远高于线段树。
复杂度分析：
时间复杂度为O(NlogN)。
AI 代码解读
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;
}
};
AI 代码解读
