逆序对计数问题C++

### 使用C++实现逆序对计数算法 #### 归并排序法计算逆序对 归并排序是一种有效的分治算法，在排序过程中可以顺便统计数组中的逆序对数量。通过修改标准的归并排序过程来记录每次右侧元素被放置到左侧未处理部分之前的情况，即可得到总的逆序对数目。 ```cpp #include <iostream> using namespace std; long long mergeAndCount(int arr[], int temp[], int left, int mid, int right) { int i = left; // 左侧子数组起始索引 int j = mid + 1; // 右侧子数组起始索引 int k = left; // 合并后的临时数组指针 long long inv_count = 0; while ((i <= mid) && (j <= right)) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; // 当前右边小于左边，则说明存在(mid-i+1)个逆序对 inv_count += (mid - i + 1); } } // 将剩余元素复制回原数组 while (i <= mid) temp[k++] = arr[i++]; while (j <= right) temp[k++] = arr[j++]; for (int p=left;p<=right;++p){ arr[p]=temp[p]; } return inv_count; } // 主函数用于调用mergeAndCount()来进行最终的结果汇总 long long _mergeSort(int arr[], int temp[], int left, int right) { long long inv_count = 0; if (right > left) { int mid = (right + left)/2; inv_count = _mergeSort(arr, temp, left, mid); // 计算左半边的数量 inv_count += _mergeSort(arr, temp, mid+1, right); // 加上右半边的数量 // 把两部分合并起来的同时加上跨越两个区域之间的逆序对数量 inv_count += mergeAndCount(arr, temp, left, mid,right); } return inv_count; } /* 接口函数 */ long long countInversions(int arr[], int n) { int *temp = new int[n]; long long ans = _mergeSort(arr,temp,0,n-1); delete[] temp; return ans; } ``` 此代码实现了基于归并排序的逆序对计数方法[^1]。该解决方案的时间复杂度为O(n log n)，其中n表示输入数组长度。 #### 树状数组（Binary Indexed Tree, BIT）/Fenwick树求解方案 另一种高效的方式是利用BIT结构在线性时间内完成查询操作，并支持动态更新数据集的能力。这种方法特别适合于频繁更改的数据序列上的逆序对统计任务。 初始化阶段建立一个辅助数组`bit[]`用来存储累积频率信息；对于每一个新加入的位置x处数值v而言，可以通过不断向其父节点位置累加贡献值的方式来维护整个区间内的频次分布情况。每当遇到一个新的待比较项y时，只需快速定位至不大于它的最大下标z，进而借助已有的累计和迅速得出当前时刻为止所形成的全部可能组合形式下的倒置关系总数目。 具体编码细节较为繁琐，这里不再赘述完整的源码片段，但上述描述提供了足够的理论基础去理解如何应用这一技巧解决问题。