树状数组求逆序对 时间复杂度

### 使用树状数组求解逆序对问题的时间复杂度分析 #### 背景介绍 树状数组（Fenwick Tree）是一种支持动态修改和查询操作的数据结构，其核心功能是对数列进行单点更新以及区间查询。通过这些特性，它可以被用来高效地解决许多涉及前缀和的问题，其中包括 **逆序对的计算**。 #### 时间复杂度分析 在使用树状数组求解逆序对问题时，主要的操作分为两部分： 1. 对树状数组执行 `update` 操作以反映当前元素的影响； 2. 执行 `query` 操作以统计小于某个特定值的数量。 每一步的具体时间复杂度如下： - 单次 `update` 和 `query` 的时间复杂度均为 \( O(\log n) \)[^1]。 - 遍历整个输入序列中的每一个元素并对其调用上述两个操作，则总共有 \( 2n \) 次这样的基本操作[^4]。 由于每次操作都是独立完成且具有相同的渐近复杂度，整体算法的时间复杂度为： \[ T(n) = O(2n \cdot \log n) = O(n \cdot \log n). \] 这表明该方法能够在合理时间内处理较大规模数据集，例如当 \( n=50,000 \) 或更大时仍能保持效率[^2]。 #### 实现细节说明 以下是基于 C++ 编写的典型代码片段展示如何利用树状数组来有效计算逆序对数量: ```cpp #include <bits/stdc++.h> using namespace std; // 定义最大数值范围 const int MAXN = 1e6 + 7; int BITree[MAXN]; void update(int idx, int val){ while(idx<MAXN){ BITree[idx]+=val; idx += (idx & (-idx)); } } int query(int idx){ int sum=0; while(idx>0){ sum+=BITree[idx]; idx -= (idx &(-idx)); } return sum; } vector<int> compress(vector<int>& nums){ vector<int> sorted_nums(nums); sort(sorted_nums.begin(),sorted_nums.end()); auto it = unique(sorted_nums.begin(),sorted_nums.end()); sorted_nums.erase(it,sorted_nums.end()); for(auto& num :nums ){ num = lower_bound(sorted_nums.begin(),sorted_nums.end(),num)-sorted_nums.begin()+1 ; } return nums; } long long countInversionsUsingBIT(const vector<int>& nums){ memset(BITree,0,sizeof(BITree)); vector<int> compressedNums =compress((vector<int>)nums); long long inversions=0; for(int i=(int)(compressedNums.size()-1);i>=0;i--){ int current_val=compressedNums[i]; // 查询比current_val小的数目 inversions += query(current_val -1 ); // 更新树状数组 update(current_val ,1 ); } return inversions; } ``` 此代码实现了完整的压缩映射过程，并展示了如何逐步构建树状数组从而精确记录每个位置上的贡献情况。 #### 结论 综上所述，采用树状数组的方法能够有效地将原本可能达到平方级别的暴力枚举方案优化至线性对数级别——即 \( O(n \cdot \log n) \)，极大地提升了大规模数据场景下的性能表现[^3]。

### 使用树状数组（Fenwick Tree）计算逆序对 #### 方法概述 树状数组是一种支持高效单点更新和前缀和查询的数据结构，其核心思想是通过一种特殊的二进制表示方法来存储部分前缀和，从而使得每次更新或查询的时间复杂度降低至 \(O(\log n)\)[^1]。对于逆序对问题，可以通过从右向左遍历数组的方式，利用树状数组记录已经访问过的元素并统计小于当前元素的数量。 具体做法如下： - 将原数组中的数值离散化为排名值，以便减少内存占用。 - 初始化一个长度等于最大排名值的树状数组。 - 从右往左依次处理每个元素，先查询该元素之前有多少个大于它的数，再将其加入树状数组中[^2]。 --- #### 核心代码实现 (C++) 以下是基于 C++ 的树状数组实现逆序对计数的具体代码： ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; // 定义树状数组类 class FenwickTree { public: vector<int> tree; int size; FenwickTree(int n) : size(n), tree(n + 1, 0) {} // 更新某个位置的值 void update(int index, int value) { while (index <= size) { tree[index] += value; index += index & (-index); } } // 查询某一段区间的前缀和 int query(int index) const { int sum = 0; while (index > 0) { sum += tree[index]; index -= index & (-index); } return sum; } }; int countInversions(vector<int>& nums) { if (nums.empty()) return 0; // 离散化过程 vector<int> sortedNums(nums.begin(), nums.end()); sort(sortedNums.begin(), sortedNums.end()); sortedNums.erase(unique(sortedNums.begin(), sortedNums.end()), sortedNums.end()); auto getRank = [&](const int& num) -> int { return lower_bound(sortedNums.begin(), sortedNums.end(), num) - sortedNums.begin() + 1; }; int rankSize = sortedNums.size(); FenwickTree fenwick(rankSize); long long inversionCount = 0; for (auto it = nums.rbegin(); it != nums.rend(); ++it) { // 反向迭代 int rank = getRank(*it); inversionCount += fenwick.query(rank - 1); // 统计前面比它小的数 fenwick.update(rank, 1); // 插入当前数 } return inversionCount; } int main() { vector<int> nums = {7, 5, 6, 4}; cout << "Number of inversions: " << countInversions(nums) << endl; // 输出应为 5 return 0; } ``` 上述代码定义了一个 `FenwickTree` 类用于管理树状数组的操作，并提供了一种通用的方式来计算任意整数序列中的逆序对数目[^3]。 --- #### 关键点解析 1. **离散化** 原始数组可能包含非常大的整数值，这会显著增加树状数组的空间需求。因此，通常需要将原始数组映射到一个小范围内的连续整数集合上，这一过程称为离散化[^4]。 2. **反向遍历** 计算逆序对的关键是从最后一个元素开始逐步向前扫描整个数组。这样做的好处是可以动态维护已知范围内所有可能出现的小于当前元素的次数。 3. **时间复杂度分析** 整个算法由两部分组成：一是排序与去重后的离散化阶段；二是实际运用树状数组完成倒置对统计的部分。总体来看，这两个环节都维持在 \(O(n \log n)\)，其中 \(n\) 表示输入列表大小。 --- ###