C++纯树状数组求逆序对

### 实现C++中的Fenwick Tree用于计算逆序对 #### 构建Fenwick Tree类 为了利用Fenwick Tree（也称为二叉索引树）来高效地处理前缀和查询以及更新操作，在C++中定义`FenwickTree`类如下[^1]： ```cpp class FenwickTree { public: explicit FenwickTree(int n) : sums_(n + 1, 0) {} // 更新指定位置及其后续节点的值 void update(int i, int delta) { while (i < static_cast<int>(sums_.size())) { sums_[i] += delta; i += lowbit(i); } } // 获取从起始至第i个元素为止的累积频率/求和 int getSum(int i) const { int sum = 0; while (i > 0) { sum += sums_[i]; i -= lowbit(i); } return sum; } private: std::vector<int> sums_; // 计算最低有效位(lowest one bit)，即x&(-x); } }; ``` #### 使用Fenwick Tree解决逆序对问题 对于给定的一个整数序列，通过遍历该序列并维护一个记录已访问数值分布情况的数据结构——这里采用的是离散化后的Fenwick Tree，能够有效地统计每一步新增加了多少个新的逆序对。 具体做法是在遇到一个新的数字时，先查找有多少个小于它的数已经被读取过；这相当于询问当前时刻之前所有小于等于其最大可能映射值得累计频次减去它自己所在的位置上的计数。之后再把新加入的那个数标记为已被看到过了即可完成一次迭代过程。 下面是完整的程序实现[^2]： ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; // ... 上述定义好的FenwickTree... long long countInversions(const vector<int>& nums) { if (nums.empty()) return 0; // 对原始数据做离散化预处理 vector<int> sortedNums(nums.begin(), nums.end()); sort(sortedNums.begin(), sortedNums.end()); auto discreteValue = [&](int val) -> int { return lower_bound(sortedNums.begin(), sortedNums.end(), val) - sortedNums.begin() + 1; }; int maxIndex = unique(sortedNums.begin(), sortedNums.end()) - sortedNums.begin(); FenwickTree ft(maxIndex); long long inversions = 0; for (auto num : nums) { int idx = discreteValue(num); inversions += ft.getSum(maxIndex) - ft.getSum(idx); ft.update(idx, 1); } return inversions; } int main(){ vector<int> arr = {7, 5, 6, 4}; // 测试用例 cout << "Number of Inversion Pairs: " << countInversions(arr) << endl; } ``` 上述代码实现了基于Fenwick Tree的逆序对数量计算方法，并提供了一个简单的测试实例验证功能正确性。在这个例子中，输入数组`arr={7,5,6,4}`将会输出总共存在多少组`(i,j)`满足条件`i<j && a[i]>a[j]`的关系对数目。