逆序數求解完全指南：歸並排序與樹狀數組兩大 O(n log n) 算法

逆序數是衡量序列「無序程度」的核心指標：對序列 S[i]，統計每個元素前面有多少比它大的元素，總和即為逆序數。例如 [4, 3, 1, 2]：

• 4 前面無元素 → 0
• 3 前面有 4 (1個) → 1
• 1 前面有 4,3 (2個) → 2
• 2 前面有 4,3 (2個，1較小不計) → 2
• 總逆序數 = 0+1+2+2 = 5

暴力雙重循環 O(n²) 只能處理小數據。本文詳細講解兩大 O(n log n) 高效算法：歸並排序法與樹狀數組法。

算法一：歸並排序法 (分治思想)

核心洞察

歸並階段合併兩個已排序子序列 L[] 和 R[] 時：

• 若取 L[i]：它前面的元素都 ≤ 它，不產生新逆序
• 若取 R[j]：說明 R[j] < L[i]，此時 L[i...end] 所有元素都比 R[j] 大且原本在它前面 → 產生 (mid - i) 個新逆序

完整代碼實現

const int MAXN = 100005;
const int INF = 1 << 30;
int L[MAXN], R[MAXN];
long long inv_count = 0;  // 逆序數可能達 n(n-1)/2，需 64 位

void Merge(int *a, int left, int mid, int right) {
    int nL = mid - left, 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 + 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++];
            inv_count += mid - i;  // 關鍵：L[i...mid-1] 共 (mid-i) 個元素 > R[j]
        }
    }
}

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

複雜度：時間 O(n log n)，空間 O(n)。優點：穩定、代碼簡潔、同步完成排序。

算法二：樹狀數組法 (Binary Indexed Tree / Fenwick Tree)

核心思想

按原序列順序處理每個元素 a[i]：

1. 查詢樹狀數組中 [1, a[i]] 的前綴和 → 已處理元素中 ≤ a[i] 的個數
2. 當前已處理總數 i 減去上述個數 → 比 a[i] 大的個數 (即以 a[i] 為右端點的逆序對數)
3. 將 a[i] 插入樹狀數組 (位置 a[i] 加 1)

離散化處理大數值

若數值範圍大 (如 10⁹)，需離散化映射至 1~n：

// 離散化：排序去重 + 二分查找映射
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

完整代碼實現

const int MAXN = 100005;
long long bit[MAXN];
int n;

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 sum = 0;
    for (; idx > 0; idx -= lowbit(idx))
        sum += bit[idx];
    return sum;
}

long long solve_bit(int *a) {
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        update(a[i], 1);
        ans += (i + 1) - query(a[i]);  // 已處理總數 - ≤a[i]的數 = >a[i]的數
    }
    return ans;
}

複雜度：時間 O(n log n)，空間 O(n)。優點：易於擴展 (如區間查詢、動態插入刪除)、適合線上處理。

兩算法對比與選擇指南

經典練習題目

• POJ 2299 - Ultra-QuickSort：純逆序數計算
• POJ 3067 - Japan：二維逆序數 (需排序 + BIT)

總結

逆序數是分治與數據結構結合的經典範例。歸並排序法思路直觀、代碼極簡，是面試首選；樹狀數組法框架通用、擴展性強，是競賽進階必備。掌握兩者，逆序數相關問題迎刃而解。