1. 逆序數

所謂逆序數，就是指一個序列S[i]，統計處於序列的每個數的比這個數大並且排在它前面的數的數目，然後對於所有數，把這個數目加起來求和就是了。

比如4 3 1 2

4第一個，所以數目為0

3的前面是4，大於3的數目為1

1的前面是4 3 ，大於1的數目為2

2的前面是4 3 1，大於2的數目為2

所以逆序數為1+2+2 = 5

求逆序數的兩種方法

常規方法是按照逆序數的規則做，結果複雜度是O(n*n)，一般來說，有兩種快速的求逆序數的方法

分別是歸併排序和樹狀陣列法

2. 歸併排序

歸併排序是源於分而治之思想，詳細的過程可以查閱其他資料，總體思想是劃分一半，各自排好序後將兩個有序序列合併起來。

如何修改歸併排序求逆序數?

首先我們假設兩個有序序列a[i]和b[i]，當合並時：

由於a[i]已是有序，所以對於a[i]的各個元素來說，排在它前面且比它大的數目都是0

當b[i]中含有比a[i]小的元素時，我們必然將b[i]元素插到前面，那麼就是說，在b[i]原先位置到該插的位置中，所有數都比b[i]大且排在它前面

所以這是b[i]的數目為新插入位置newPos - 原來位置oldPos