最初接触到逆序数是在离散数学中，逆序数的概念如下：

给出一个有N个数的序列，如果一对数中前面的数大于后面的数，那么它们就称为一个逆序。一个序列中逆序的总数就称为这个排列的逆序数。
如序列 2 4 3 1 的逆序数为4（2和1，4和3，4和1，3和1）

逆序数的解法有多种，这里介绍归并排序、树状数组，时间复杂度均为O(n log n)
[TOC]

归并求解逆序数

算法思想

• 从问题的源头出发，如果前面大于后面，就构成一组逆序，而这就是归并排序中交换两个数的条件；
• 结构体a[].val存储值， a[].num存储逆序组数
• 因为只计算逆序数，对于一组逆序只用标记1次即可，这里将对较大的数进行记录。

如对于 2 4 3 1 只标记较大数，逆序记录为 1 2 1 0
归并后的结果：
a[].val 1 2 3 4
a[].num 0 1 1 2

———————————————开始归并—————————————————

#include <iostream>

using namespace std;

const int maxn = 100005;
struct note{
	int val;
	int num;//逆序 
};
struct note a[maxn], b[maxn];
void Merge(int l, int mid, int r){
	int i = l, j = mid+1;
	int k = l;
	while(i <= mid && j <= r){
		if(a[i].val <= a[j].val){
			b[k++] = a[i++];
			b[k-1].num += (j-mid-1);
		}else{
			b[k++] = a[j++];
			//b[k-1].num += (mid-i+1);	
		}
	}
	while(i <= mid){
		b[k++] = a[i++];
		b[k-1].num += (r-mid);
	}
	while(j <= r){
		b[k++] = a[j++];
	}
	for(k = l; k <= r; ++k){
		a[k] = b[k];
	}
}
void MergeSort(int l, int r){
	if(l < r){
		int mid = (l+r) >> 1;
		MergeSort(l, mid);
		MergeSort(mid+1, r);
		Merge(l, mid, r);
	}
}
int main(){
	int n;
	cin >> n;
	for(int i = 0; i < n; ++i){
		cin >> a[i].val;
	}
	MergeSort(0, n-1);
	int ans = 0;
	for(int i = 0; i < n; ++i){//逆序数即逆序的组数累加
		ans += a[i].num;
	}
	cout << ans <<endl;
	return 0;
}

其实记录逆序的过程有助于对归并过程的加深理解；
解释一下Merge()中的这两行吧：
b[k-1].num += (r-mid);
b[k-1].num += (j-mid-1);
正因为Merge()是对两组有序的序列合并，所以这两行记录的是，a[i].val后面比它小的有多少；

• ***注：如果要求出逆序对，那么既要记录a[i].val后面比它小的组数，还要记录前面比它大的组数；
  其实只加一行代码即可，就是注释掉的那句
  //b[k-1].num += (mid-i+1);
  同样对于 2 4 3 1 各组逆序对结果：
  1 2 1 0
  0 0 1 3
  归并后的结果为：
  a[].val 1 2 3 4
  a[].num 3 1 2 3

树状数组求解逆序数

• 同样从问题的源头出发，还是对于一组逆序，这里只对较大的数进行标记
• 记录a[i]后面有多少个小于它的数，显然这需要从后往前遍历
  对于 2 4 3 1 从后往前记录逆序 1 2 1 0
  粗暴的方法当然是两层循环了，可以结合树状数组的好处（单点更新、区间求和）进行改进
  有关树状数组的介绍可以参考我的另一篇博客：
  

算法思想

1. 构建C[1:n]的树状数组（考虑到a[]可能数据过大，可以离散化一下，后面会有介绍），初始化为0
2. 从后往前遍历时，单值更新a[i]+1，区间加1即可，每次单值查询即可

还原一下逆序遍历2 4 3 1过程中录入C[]的原数据 A[]的变化吧

C[]的原数据 A[]:
A[1] A[2] A[3] A[4]
0 1 0 0
0 1 0 1
0 1 0 1
0 1 1 1
单点更新即可，树状数组实现对其区间求和依次为0 1 2 1，最后累加得到逆序数
———————————————完整代码———————————————————

#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 100005;
int n;
int tree[maxn], Hash[maxn];
int data[maxn];
struct note{
    int value;
    int index;
}a[maxn];
bool comp(struct note x, struct note y){
    return x.value < y.value;
}
int lowbit(int x){
    return x&(-x);
}
void updata(int i, int temp){
    while(i <= n){
        tree[i] += temp;
        i += lowbit(i);
    }
}
int getsum(int i){
    int res = 0;
    while(i > 0){
        res += tree[i];
        i -= lowbit(i);
    }
    return res;
}
int main(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> a[i].value;
        a[i].index = i;
    }//离散化
    sort(a+1, a+n+1, comp);
    for(int i = 1; i <= n; ++i){
        if(i != 1 && a[i].value == a[i-1].value)
            Hash[a[i].index] = Hash[a[i-1].index];
        else
            Hash[a[i].index] = i;
    }
    int ans = 0;
    for(int i = n; i >= 1; --i){
        //cout << getsum(Hash[i]) <<" ";
        ans += getsum(Hash[i]);
        if(Hash[i] != n){
            updata(Hash[i]+1, 1);
        }
    }
    cout << ans << endl;

    return 0;
}

***注：不就是单点更新，区间求和吗，线段树也可以搞定，但还是树状数组实现起来简单些

·【蓝桥】·小朋友排队