逆序數求解完全指南：歸併排序法與樹狀數組法詳解

逆序數是衡量序列「無序程度」的核心指標。定義：對序列 S[i]，統計每個元素前方比它大的元素個數，總和即為逆序數。例：4 3 1 2 的逆序數 = 0+1+2+2 = 5。

方法一：歸併排序改造（O(n log n)）

核心洞察：歸併階段合併兩個有序子陣列 L、R 時，若 R[j] < L[i]，則 L[i..end] 全部大於 R[j] 且位於其前方，貢獻逆序數 mid - i + 1。

const int MAXN = 100005;
const int INF = 1 << 30;
int L[MAXN], R[MAXN];
long long invCount = 0;

void Merge(int* a, int left, int mid, int right) {
    int nL = mid - left + 1;
    int nR = right - mid;
    for (int i = 0; i < nL; ++i) L[i] = a[left + i];
    for (int i = 0; i < nR; ++i) R[i] = a[mid + 1 + i];
    L[nL] = R[nR] = INF;  // 哨兵
    
    int i = 0, j = 0;
    for (int k = left; k <= right; ++k) {
        if (L[i] <= R[j]) a[k] = L[i++];
        else {
            a[k] = R[j++];
            invCount += nL - i;  // 關鍵：剩餘左半部元素皆大於 R[j]
        }
    }
}

void MergeSort(int* a, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        MergeSort(a, left, mid);
        MergeSort(a, mid+1, right);
        Merge(a, left, mid, right);
    }
}

方法二：樹狀數組（Binary Indexed Tree，O(n log n)）

適用場景：數值範圍大需離散化；需線上查詢/動態更新。

原理：按原序遍歷元素 a[i]，插入 BIT（update(a[i], 1)），查詢當前 ≤ a[i] 的個數 sum(a[i])，則大於 a[i] 的個數 = i - sum(a[i])，累加即得逆序數。

long long BIT[MAXN];
int N;

inline int lowbit(int x) { return x & (-x); }

void update(int idx, int val) {
    for (; idx <= N; idx += lowbit(idx)) BIT[idx] += val;
}

long long query(int idx) {
    long long res = 0;
    for (; idx > 0; idx -= lowbit(idx)) res += BIT[idx];
    return res;
}

// 離散化輔助
vector<int> vals(a, a+n);
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
for (int i = 0; i < n; ++i)
    a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin() + 1; // 1-based

N = vals.size();
long long ans = 0;
for (int i = 0; i < n; ++i) {
    update(a[i], 1);
    ans += (i + 1) - query(a[i]);
}

經典練習題

• POJ 2299 - Ultra-QuickSort
• POJ 3067 - Japan

選型建議

掌握兩種方法，逆序數問題迎刃而解。