树状数组求逆序对 – 世子之争，素来如此

逆序对计数示例（基于树状数组）

逆序对（Inversion）是指数组中前面的元素大于后面的元素的对数，即若 i < j 且 a[i] > a[j]，则 (a[i], a[j]) 是一个逆序对。树状数组可以高效统计逆序对数量，步骤如下：

算法步骤

离散化（可选）：
- 若元素值范围很大（如 1e9），需先将数组离散化为 1..n 的排名，保持大小关系不变。
从右向左遍历：
- 对每个元素 a[i]，查询树状数组中小于 a[i] 的元素数量（即已处理元素中比 a[i] 小的数的个数）。
- 逆序对数量 += i - query(a[i])（当前元素右侧比它小的数的个数）。
- 将 a[i] 插入树状数组（update(a[i], 1)）。

C++ 实现

#include <vector>
#include <algorithm>
using namespace std;

class FenwickTree {
private:
    vector<int> tree;
    int lowbit(int x) { return x & -x; }
public:
    FenwickTree(int n) : tree(n + 1, 0) {}
    void update(int x, int delta) {
        while (x < tree.size()) {
            tree[x] += delta;
            x += lowbit(x);
        }
    }
    int query(int x) {
        int res = 0;
        while (x > 0) {
            res += tree[x];
            x -= lowbit(x);
        }
        return res;
    }
};

int countInversions(vector<int>& nums) {
    // 离散化（将原数组映射到1..n的排名）
    vector<int> sorted = nums;
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    
    // 离散化后的数组
    for (int& num : nums) {
        num = lower_bound(sorted.begin(), sorted.end(), num) - sorted.begin() + 1;
    }

    FenwickTree ft(nums.size());
    int res = 0;
    // 从右向左遍历
    for (int i = nums.size() - 1; i >= 0; --i) {
        res += ft.query(nums[i] - 1); // 统计比nums[i]小的数的个数
        ft.update(nums[i], 1);        // 插入当前数
    }
    return res;
}

示例分析
输入数组：[3, 1, 4, 2]

离散化后：[2, 1, 3, 4]（原值 3 的排名为 2，1 的排名为 1，依此类推）。
从右向左处理：
- i=3（值 4）：query(3-1)=0，逆序对 +=0，插入 4。
- i=2（值 2）：query(2-1)=1（1 比 2 小），逆序对 +=1，插入 2。
- i=1（值 1）：query(1-1)=0，逆序对 +=0，插入 1。
- i=0（值 3）：query(2-1)=1（1 比 3 小），逆序对 +=1，插入 3。
总逆序对：0 + 1 + 0 + 1 = 2（实际逆序对为 (3,1) 和 (4,2)）。