“逆序对”归并和线段树两种解法。这道经典题存在于任何一个算法题库中，故单独拿出分析讨论。
暴力
如果仅仅是用暴力、普通的分治方法。遇到数据量较大时内存不够。
归并
归并排序的时间复杂度
用归并法解此题之前先考虑一下，为何归并排序的时间复杂度是\(O(nlog_n)\)？
答：
首先是分裂，导致大小为n的数组散开形成\(log_n\)层，然后归并的亮点在于合并这些分裂开的数组：
两个原本有序的数组，合并的复杂度只需要\(O( n )\)啊！（当然，需要一个长度为n的辅助数组，空间换时间）
如果两个普通数组，合并时两两比较，复杂度就是\(O(n^2)\)。
分析到这里，再看看我之前写的归并法解此题，完全没领悟到归并的精髓啊！
最终代码
(就是归并排序多加一句对ans操作)：
void merge(vector<int> &data,int i1,int j1,int i2,int j2){
vector<int > tmp;
int i=i1;
while (i1<=j1 && i2<=j2){
if(data[i1]<=data[i2]){
tmp.push_back(data[i1++]);
} else{
tmp.push_back(data[i2++]);
ans+=j1-i1+1;
}
}
while (i1<=j1)
tmp.push_back(data[i1++]);
while (i2<=j2)
tmp.push_back(data[i2++]);
for(int x:tmp)
data[i++]=x;
return;
}
ans要声明成long long型，因为5e5大小的数组传进来，随便有几个逆序的ans就好大。
注意两个点：
-
二分时要分割成(i,m,m+1,j)
不要分成(i,m-1,m,j)这样(1,2)区间会被分成:
(1,0,1,2)无限循环进入(1,2)
-
合并时的条件是(i<=m && m+1<=j)
要带上等于号！
因为不能保证两个式子都是小于的。万一有一个等于就无法进入合并了。
比如(1,2,3,3) 虽然(3,3)不用处理，但是（1,2）要处理啊。