在C++中使用Fenwick树(二进制索引树)统计插入排序的移位数

#include <iostream>
#include <vector>

using namespace std;

// Fenwick树类
class FenwickTree {
private:
    vector<int> tree;

public:
    FenwickTree(int n) {
        tree.resize(n + 1, 0);
    }

    // 更新Fenwick树中的元素
    void update(int index, int delta) {
        while (index < tree.size()) {
            tree[index] += delta;
            index += index & -index;
        }
    }

    // 计算前缀和
    int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= index & -index;
        }
        return sum;
    }
};

// 统计插入排序的移位数
int countInversions(vector<int>& nums) {
    int n = nums.size();
    FenwickTree tree(n);
    int inversions = 0;

    for (int i = n - 1; i >= 0; i--) {
        inversions += tree.query(nums[i] - 1);
        tree.update(nums[i], 1);
    }

    return inversions;
}

int main() {
    vector<int> nums = {4, 3, 1, 2};
    int inversions = countInversions(nums);
    cout << "插入排序的移位数为：" << inversions << endl;

    return 0;
}