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

在C++中使用Fenwick树（也称为二进制索引树）可以用于统计插入排序的移位数。Fenwick树是一种高效的数据结构，用于支持动态数组的前缀和查询和更新操作。

插入排序的移位数是指在对一个数组进行插入排序时，需要移动元素的总次数。通过使用Fenwick树，我们可以在O(log n)的时间复杂度内计算出插入排序的移位数。

下面是使用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;
}

在上述代码中，我们首先定义了一个FenwickTree类，其中包含了update和query两个操作，分别用于更新Fenwick树中的元素和计算前缀和。然后，我们使用Fenwick树来统计插入排序的移位数。

对于给定的数组，我们从最后一个元素开始遍历，每次查询比当前元素小的元素个数，并将其累加到移位数中。然后，我们更新Fenwick树中对应元素的计数。最后，返回移位数即可。

Fenwick树的优势在于其高效的查询和更新操作，使得统计插入排序的移位数的时间复杂度为O(n log n)。它适用于需要频繁进行前缀和查询和更新的场景，例如计算逆序对、计算数组中小于等于某个值的元素个数等。

腾讯云相关产品和产品介绍链接地址：