1. 从一道经典面试题说起为什么是树状数组如果你刷过一些算法题或者参加过技术面试大概率遇到过“逆序对”问题。题目描述很简单给定一个整数数组统计其中有多少对元素(i, j)满足i j且nums[i] nums[j]。比如数组[2, 4, 1, 3, 5]逆序对有(2,1),(4,1),(4,3)总共3对。最直观的解法是双层循环暴力枚举时间复杂度 O(n²)在数据量稍大比如 n 10⁵时立刻超时。于是我们自然想到用更高效的算法而归并排序的分治思想是教科书级的 O(n log n) 解法。但今天我想和你深入聊聊另一个同样高效且在特定场景下更具优势的工具——树状数组。为什么在归并排序已经足够好的情况下还要掌握树状数组原因有三。第一思维转换。归并排序求解逆序数的过程融合在排序中理解起来需要递归分治的思维。而树状数组的解法更“直接”它清晰地分离了“统计”和“排序”两个动作核心是动态维护一个频率数组的前缀和这种“单点更新、区间查询”的模型是许多更复杂问题的基础。第二空间与灵活度。归并排序通常需要 O(n) 的额外空间用于合并且过程会改变原数组顺序。树状数组解法在离散化后空间消耗与值域相关且不破坏原数组。第三可扩展性。一旦你掌握了用树状数组求逆序数的“模板”你实际上就掌握了一类问题的通解比如求“正序对”、“某个值左侧小于它的个数”甚至是二维偏序问题思路一脉相承。所以这个“模板”的价值远不止于解决一道题。它是一个精巧的数据结构思想的载体是打开“高效统计”世界的一把钥匙。接下来我将彻底拆解这个模板从原理到细节从实现到避坑让你不仅能“套用”更能“懂得”和“活用”。2. 核心思想拆解如何用树状数组“数”逆序对要理解模板必须先吃透其背后的逻辑。我们暂时忘掉树状数组这个数据结构先思考一个更本质的问题如何高效地统计逆序对假设我们有一个数组arr [5, 2, 6, 1, 3]。一种思路是模拟过程从左到右或从右到左遍历每个元素对于当前元素arr[i]我们想知道在它之前或之后有多少个元素比它大或小。这本质上是一个动态查询与更新的过程。以从后往前遍历为例这样对于当前元素arr[i]我们关心的是在它后面已经遍历过的元素中有多少个比它小因为i j且arr[i] arr[j]当 j 在 i 后面时条件等价于查询已遍历的、值小于arr[i]的元素个数。我们需要一个数据结构来维护这个“已遍历元素值的集合”并快速回答“集合里有多少个数小于等于 x”这样的查询。同时每遍历一个新元素我们就要把它加入这个集合。这不正是前缀和的用武之地吗我们可以设想一个巨大的数组freq[]它的下标代表可能的数值值代表这个数值出现的次数。那么“小于等于 x 的元素个数”就是freq[1] freq[2] ... freq[x]即前缀和prefix_sum(x)。加入一个值为v的元素就是执行freq[v] 1。于是算法框架就清晰了从后往前遍历原数组。对于当前元素的值v查询freq[1...v-1]的前缀和即已遍历中小于v的元素个数这个个数就是以v作为较小数的逆序对数量累加到答案中。将v加入集合即执行freq[v] 1。这个框架的瓶颈在于如果数值范围很大比如v最大是 10⁹我们不可能真的开一个那么大的freq数组。同时单点更新和前缀和查询如果朴素实现都是 O(n)总复杂度会退化为 O(n²)。这时树状数组就登场了。它能将单点更新和前缀和查询的复杂度都优化到 O(log n)其中 n 是值域离散化后的大小。所以树状数组在这里扮演的角色就是一个支持高效单点增加、高效前缀和查询的动态频率数组。整个算法的核心驱动力就是上述的遍历与统计思想树状数组是加速这一过程的引擎。3. 模板实现逐行精讲理解了思想我们来看代码实现。一个完整的、鲁棒的树状数组求逆序数模板通常包含以下几个部分离散化、树状数组类、主逻辑。下面我们逐一拆解。3.1 离散化处理压缩值域的关键一步由于数值可能很大直接作为数组下标不现实。离散化将原始数组中的每个值映射到一个从 1 开始的连续正整数排名上。这样值域大小就被压缩到了数组长度 n树状数组的大小只需开到 n5多加一点防止边界问题。vectorint discrete(vectorint nums) { vectorint tmp nums; sort(tmp.begin(), tmp.end()); tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end()); // 去重 for (int num : nums) { num lower_bound(tmp.begin(), tmp.end(), num) - tmp.begin() 1; // 映射到 1~n } return nums; // 返回离散化后的数组 }注意这里一定要映射到1开始因为树状数组的下标操作通常基于lowbit运算从 1 开始设计是最自然和安全的。映射到 0 会导致死循环或错误。3.2 树状数组类封装理解lowbit与操作树状数组的精髓在于lowbit运算x -x它取出x二进制表示中最低位的 1 及其后面的 0。这个操作决定了更新和查询的跳跃路径。class Fenwick { private: vectorint tree; int n; public: Fenwick(int size) : n(size), tree(size 1, 0) {} // 单点增加在位置 idx 的值上加 val void add(int idx, int val) { while (idx n) { tree[idx] val; idx idx -idx; // 跳到父节点 } } // 前缀和查询求 [1, idx] 的和 int query(int idx) { int sum 0; while (idx 0) { sum tree[idx]; idx - idx -idx; // 跳到前一个区间节点 } return sum; } };add操作从idx开始不断加上lowbit(idx)向上跳更新沿途所有包含该点的区间和。这保证了后续查询更大区间时能包含这次更新。query操作从idx开始不断减去lowbit(idx)向前跳累加一个个不重叠的、长度为lowbit的区间和最终拼出[1, idx]的总和。这两个 O(log n) 的操作正是我们高效维护频率数组freq的基石。3.3 主逻辑组装遍历、查询与更新将离散化和树状数组组合起来就是主逻辑。这里采用从后往前遍历的写法它更符合直觉查询已遍历的小于当前值的数量。long long countInversions(vectorint nums) { if (nums.empty()) return 0; // 1. 离散化 vectorint arr discrete(nums); // arr 中元素现在是 1~n 的整数 int n *max_element(arr.begin(), arr.end()); // 离散化后的最大值即值域大小 Fenwick bit(n); long long ans 0; // 2. 从后往前遍历 for (int i arr.size() - 1; i 0; --i) { int x arr[i]; // 查询当前已遍历的数中值小于 x 的有多少个 // query(x-1) 得到的是 freq[1] ... freq[x-1] 的和 ans bit.query(x - 1); // 将当前数放入树状数组频率1 bit.add(x, 1); } return ans; }为什么是query(x-1)因为逆序对的定义是arr[i] arr[j]。当我们从后往前遍历到arr[i]值为x时bit中存储的是所有下标大于i的元素的频率。我们想知道这些“后面的元素”里有多少个值比x小这样arr[i] arr[j]才成立。所以查询的是值在[1, x-1]这个区间的元素总数即query(x-1)。复杂度分析离散化 O(n log n)树状数组的 n 次查询和更新 O(n log n)总复杂度 O(n log n)。空间复杂度 O(n)。4. 关键细节、变种与边界处理一个可靠的模板必须能处理各种边界情况和需求变种。以下是几个关键点4.1 遍历方向与查询含义的对应关系模板中采用了从后往前遍历。其实从前往后遍历也可以但查询的含义会发生变化。从后往前如上模板对于nums[i]查询的是i之后且值小于nums[i]的元素个数。对应query(rank-1)。从前往后对于nums[i]查询的是i之前且值大于nums[i]的元素个数。这需要查询的是值在[rank1, n]区间的总数。可以通过query(n) - query(rank)得到。两种方式结果相同但个人认为从后往前的逻辑更直接。4.2 处理重复元素离散化中的unique操作确保了每个值有唯一的排名。这在求逆序数时是正确的。因为逆序对关心的是“大于”关系值相等的元素不构成逆序对。我们的query(x-1)只查询严格小于当前值的数自然排除了等值的情况。4.3 答案可能很大使用long long逆序对的数量最多可达n*(n-1)/2对于n10⁵的情况结果可能超过 32 位整型 (int) 的范围约 2.1e9。因此累加答案的变量ans必须使用long long64位整型。4.4 变种问题求正序对、求左侧小于当前数的个数稍微修改查询和更新的逻辑这个模板可以解决一系列类似问题。求正序对顺序对即i j且nums[i] nums[j]。从前往后遍历对于nums[i]查询已遍历的数中值小于它的个数即query(rank-1)然后累加再更新。这实际上统计了每个数作为较大数时前面有多少个比它小的数。求每个数左侧小于它的个数这就是正序对问题的子集遍历和查询方式完全一样只是把每次query(rank-1)的结果存下来而不是累加到一个总和里。// 求每个元素左侧小于它的元素个数 vectorint countSmallerToLeft(vectorint nums) { vectorint arr discrete(nums); int n *max_element(arr.begin(), arr.end()); Fenwick bit(n); vectorint res(nums.size(), 0); for (int i 0; i arr.size(); i) { int x arr[i]; res[i] bit.query(x - 1); // 查询左侧小于当前值的个数 bit.add(x, 1); // 将当前值加入集合 } return res; }5. 实战踩坑与性能优化心得在实际做题和工程化时一些细节决定了代码的正确性和效率。5.1 离散化中的“去重”与“不去重”我们的模板使用了去重 (unique)。这在纯粹求逆序数时没问题。但在一些变种问题里比如需要保留原数组顺序进行其他操作或者离散化后的排名需要严格对应原值即使重复就不能去重。此时lower_bound仍然适用它会给相同的值返回相同的排名符合“值相等则排名相同”的需求。是否需要去重取决于具体问题定义。5.2 树状数组大小与初始化树状数组tree的大小应设为离散化后的最大值 1。通常我会开n 5或n 10提供一个小的缓冲防止边界写错。初始化时所有元素为 0表示初始频率均为 0。5.3 警惕“下标1”的约定这是最容易出错的地方。整个逻辑离散化映射到1、add和query循环条件idx n和idx 0都依赖于下标从1开始。如果在离散化时映射到了0或者在query(x-1)时x可能为1此时x-10query(0)会直接返回0逻辑上没错但必须确保add操作不会传入0。一个健壮的写法是在离散化后可以检查一下最小值是否为1或者在任何可能传入0的地方进行判断。5.4 与归并排序解法的对比选择虽然两者时间复杂度相同但常数上有差异。树状数组涉及离散化排序、去重、二分查找和多次 log n 操作常数比归并排序略大。但在内存访问模式上树状数组的连续更新/查询可能对缓存更友好。对于纯粹的逆序对问题两者均可。选择树状数组的理由更在于其“可扩展性”在线查询归并排序是离线的必须拿到所有数据后才能计算。树状数组可以支持数据流式输入每来一个数就能知道当前逆序对总数从后往前遍历的思路需要调整。支持修改如果题目要求支持修改某个位置的值并重新查询逆序数归并排序需要全部重算 O(n log n)。而树状数组可以模拟这个过程先减去原值的影响再增加新值的影响每次修改 O(log n)。更高维度对于二维偏序问题如“求满足x_i x_j且y_i y_j的点对”可以通过对一维排序另一维用树状数组维护来解决这是归并排序难以直接处理的。5.5 一个完整的、带注释的鲁棒模板结合以上所有点这里给出一个我更倾向于在竞赛或面试中使用的版本它包含了防御性检查和一些习惯写法。#include vector #include algorithm using namespace std; class Fenwick { vectorint bit; int n; public: Fenwick(int n) : n(n), bit(n 1, 0) {} void add(int idx, int delta) { // 习惯用 while (idx n) 而不是 idx bit.size()更清晰 for (; idx n; idx idx -idx) bit[idx] delta; } int sum(int idx) { int s 0; for (; idx 0; idx - idx -idx) s bit[idx]; return s; } // 可选查询区间 [l, r] 的和 int rangeSum(int l, int r) { if (l r) return 0; return sum(r) - sum(l - 1); } }; // 离散化函数返回映射后的数组 vectorint discretize(vectorint a) { vectorint b a; sort(b.begin(), b.end()); b.erase(unique(b.begin(), b.end()), b.end()); vectorint res(a.size()); for (int i 0; i a.size(); i) { // lower_bound 返回的是迭代器相减得到下标1 映射到 [1, m] res[i] lower_bound(b.begin(), b.end(), a[i]) - b.begin() 1; } return res; } long long countInversions(vectorint nums) { if (nums.size() 2) return 0; // 边界情况 vectorint arr discretize(nums); int maxVal *max_element(arr.begin(), arr.end()); Fenwick ft(maxVal); long long ans 0; // 从后往前遍历 for (int i (int)arr.size() - 1; i 0; --i) { ans ft.sum(arr[i] - 1); // 查询小于当前值的数量 ft.add(arr[i], 1); // 插入当前值 } return ans; }这个模板清晰、模块化并且将树状数组封装成类方便复用。discretize函数返回新的数组不破坏输入这也是一个良好的实践。掌握这个模板你收获的不仅仅是一个求逆序数的工具更是一种利用高效数据结构维护动态前缀和来解决统计问题的通用思维。下次遇到类似“动态排名”、“实时统计小于某值的个数”这些问题时不妨先想想是不是可以请出树状数组这位老朋友。 树状数组解逆序对：从原理到模板的算法精讲
1. 从一道经典面试题说起为什么是树状数组如果你刷过一些算法题或者参加过技术面试大概率遇到过“逆序对”问题。题目描述很简单给定一个整数数组统计其中有多少对元素(i, j)满足i j且nums[i] nums[j]。比如数组[2, 4, 1, 3, 5]逆序对有(2,1),(4,1),(4,3)总共3对。最直观的解法是双层循环暴力枚举时间复杂度 O(n²)在数据量稍大比如 n 10⁵时立刻超时。于是我们自然想到用更高效的算法而归并排序的分治思想是教科书级的 O(n log n) 解法。但今天我想和你深入聊聊另一个同样高效且在特定场景下更具优势的工具——树状数组。为什么在归并排序已经足够好的情况下还要掌握树状数组原因有三。第一思维转换。归并排序求解逆序数的过程融合在排序中理解起来需要递归分治的思维。而树状数组的解法更“直接”它清晰地分离了“统计”和“排序”两个动作核心是动态维护一个频率数组的前缀和这种“单点更新、区间查询”的模型是许多更复杂问题的基础。第二空间与灵活度。归并排序通常需要 O(n) 的额外空间用于合并且过程会改变原数组顺序。树状数组解法在离散化后空间消耗与值域相关且不破坏原数组。第三可扩展性。一旦你掌握了用树状数组求逆序数的“模板”你实际上就掌握了一类问题的通解比如求“正序对”、“某个值左侧小于它的个数”甚至是二维偏序问题思路一脉相承。所以这个“模板”的价值远不止于解决一道题。它是一个精巧的数据结构思想的载体是打开“高效统计”世界的一把钥匙。接下来我将彻底拆解这个模板从原理到细节从实现到避坑让你不仅能“套用”更能“懂得”和“活用”。2. 核心思想拆解如何用树状数组“数”逆序对要理解模板必须先吃透其背后的逻辑。我们暂时忘掉树状数组这个数据结构先思考一个更本质的问题如何高效地统计逆序对假设我们有一个数组arr [5, 2, 6, 1, 3]。一种思路是模拟过程从左到右或从右到左遍历每个元素对于当前元素arr[i]我们想知道在它之前或之后有多少个元素比它大或小。这本质上是一个动态查询与更新的过程。以从后往前遍历为例这样对于当前元素arr[i]我们关心的是在它后面已经遍历过的元素中有多少个比它小因为i j且arr[i] arr[j]当 j 在 i 后面时条件等价于查询已遍历的、值小于arr[i]的元素个数。我们需要一个数据结构来维护这个“已遍历元素值的集合”并快速回答“集合里有多少个数小于等于 x”这样的查询。同时每遍历一个新元素我们就要把它加入这个集合。这不正是前缀和的用武之地吗我们可以设想一个巨大的数组freq[]它的下标代表可能的数值值代表这个数值出现的次数。那么“小于等于 x 的元素个数”就是freq[1] freq[2] ... freq[x]即前缀和prefix_sum(x)。加入一个值为v的元素就是执行freq[v] 1。于是算法框架就清晰了从后往前遍历原数组。对于当前元素的值v查询freq[1...v-1]的前缀和即已遍历中小于v的元素个数这个个数就是以v作为较小数的逆序对数量累加到答案中。将v加入集合即执行freq[v] 1。这个框架的瓶颈在于如果数值范围很大比如v最大是 10⁹我们不可能真的开一个那么大的freq数组。同时单点更新和前缀和查询如果朴素实现都是 O(n)总复杂度会退化为 O(n²)。这时树状数组就登场了。它能将单点更新和前缀和查询的复杂度都优化到 O(log n)其中 n 是值域离散化后的大小。所以树状数组在这里扮演的角色就是一个支持高效单点增加、高效前缀和查询的动态频率数组。整个算法的核心驱动力就是上述的遍历与统计思想树状数组是加速这一过程的引擎。3. 模板实现逐行精讲理解了思想我们来看代码实现。一个完整的、鲁棒的树状数组求逆序数模板通常包含以下几个部分离散化、树状数组类、主逻辑。下面我们逐一拆解。3.1 离散化处理压缩值域的关键一步由于数值可能很大直接作为数组下标不现实。离散化将原始数组中的每个值映射到一个从 1 开始的连续正整数排名上。这样值域大小就被压缩到了数组长度 n树状数组的大小只需开到 n5多加一点防止边界问题。vectorint discrete(vectorint nums) { vectorint tmp nums; sort(tmp.begin(), tmp.end()); tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end()); // 去重 for (int num : nums) { num lower_bound(tmp.begin(), tmp.end(), num) - tmp.begin() 1; // 映射到 1~n } return nums; // 返回离散化后的数组 }注意这里一定要映射到1开始因为树状数组的下标操作通常基于lowbit运算从 1 开始设计是最自然和安全的。映射到 0 会导致死循环或错误。3.2 树状数组类封装理解lowbit与操作树状数组的精髓在于lowbit运算x -x它取出x二进制表示中最低位的 1 及其后面的 0。这个操作决定了更新和查询的跳跃路径。class Fenwick { private: vectorint tree; int n; public: Fenwick(int size) : n(size), tree(size 1, 0) {} // 单点增加在位置 idx 的值上加 val void add(int idx, int val) { while (idx n) { tree[idx] val; idx idx -idx; // 跳到父节点 } } // 前缀和查询求 [1, idx] 的和 int query(int idx) { int sum 0; while (idx 0) { sum tree[idx]; idx - idx -idx; // 跳到前一个区间节点 } return sum; } };add操作从idx开始不断加上lowbit(idx)向上跳更新沿途所有包含该点的区间和。这保证了后续查询更大区间时能包含这次更新。query操作从idx开始不断减去lowbit(idx)向前跳累加一个个不重叠的、长度为lowbit的区间和最终拼出[1, idx]的总和。这两个 O(log n) 的操作正是我们高效维护频率数组freq的基石。3.3 主逻辑组装遍历、查询与更新将离散化和树状数组组合起来就是主逻辑。这里采用从后往前遍历的写法它更符合直觉查询已遍历的小于当前值的数量。long long countInversions(vectorint nums) { if (nums.empty()) return 0; // 1. 离散化 vectorint arr discrete(nums); // arr 中元素现在是 1~n 的整数 int n *max_element(arr.begin(), arr.end()); // 离散化后的最大值即值域大小 Fenwick bit(n); long long ans 0; // 2. 从后往前遍历 for (int i arr.size() - 1; i 0; --i) { int x arr[i]; // 查询当前已遍历的数中值小于 x 的有多少个 // query(x-1) 得到的是 freq[1] ... freq[x-1] 的和 ans bit.query(x - 1); // 将当前数放入树状数组频率1 bit.add(x, 1); } return ans; }为什么是query(x-1)因为逆序对的定义是arr[i] arr[j]。当我们从后往前遍历到arr[i]值为x时bit中存储的是所有下标大于i的元素的频率。我们想知道这些“后面的元素”里有多少个值比x小这样arr[i] arr[j]才成立。所以查询的是值在[1, x-1]这个区间的元素总数即query(x-1)。复杂度分析离散化 O(n log n)树状数组的 n 次查询和更新 O(n log n)总复杂度 O(n log n)。空间复杂度 O(n)。4. 关键细节、变种与边界处理一个可靠的模板必须能处理各种边界情况和需求变种。以下是几个关键点4.1 遍历方向与查询含义的对应关系模板中采用了从后往前遍历。其实从前往后遍历也可以但查询的含义会发生变化。从后往前如上模板对于nums[i]查询的是i之后且值小于nums[i]的元素个数。对应query(rank-1)。从前往后对于nums[i]查询的是i之前且值大于nums[i]的元素个数。这需要查询的是值在[rank1, n]区间的总数。可以通过query(n) - query(rank)得到。两种方式结果相同但个人认为从后往前的逻辑更直接。4.2 处理重复元素离散化中的unique操作确保了每个值有唯一的排名。这在求逆序数时是正确的。因为逆序对关心的是“大于”关系值相等的元素不构成逆序对。我们的query(x-1)只查询严格小于当前值的数自然排除了等值的情况。4.3 答案可能很大使用long long逆序对的数量最多可达n*(n-1)/2对于n10⁵的情况结果可能超过 32 位整型 (int) 的范围约 2.1e9。因此累加答案的变量ans必须使用long long64位整型。4.4 变种问题求正序对、求左侧小于当前数的个数稍微修改查询和更新的逻辑这个模板可以解决一系列类似问题。求正序对顺序对即i j且nums[i] nums[j]。从前往后遍历对于nums[i]查询已遍历的数中值小于它的个数即query(rank-1)然后累加再更新。这实际上统计了每个数作为较大数时前面有多少个比它小的数。求每个数左侧小于它的个数这就是正序对问题的子集遍历和查询方式完全一样只是把每次query(rank-1)的结果存下来而不是累加到一个总和里。// 求每个元素左侧小于它的元素个数 vectorint countSmallerToLeft(vectorint nums) { vectorint arr discrete(nums); int n *max_element(arr.begin(), arr.end()); Fenwick bit(n); vectorint res(nums.size(), 0); for (int i 0; i arr.size(); i) { int x arr[i]; res[i] bit.query(x - 1); // 查询左侧小于当前值的个数 bit.add(x, 1); // 将当前值加入集合 } return res; }5. 实战踩坑与性能优化心得在实际做题和工程化时一些细节决定了代码的正确性和效率。5.1 离散化中的“去重”与“不去重”我们的模板使用了去重 (unique)。这在纯粹求逆序数时没问题。但在一些变种问题里比如需要保留原数组顺序进行其他操作或者离散化后的排名需要严格对应原值即使重复就不能去重。此时lower_bound仍然适用它会给相同的值返回相同的排名符合“值相等则排名相同”的需求。是否需要去重取决于具体问题定义。5.2 树状数组大小与初始化树状数组tree的大小应设为离散化后的最大值 1。通常我会开n 5或n 10提供一个小的缓冲防止边界写错。初始化时所有元素为 0表示初始频率均为 0。5.3 警惕“下标1”的约定这是最容易出错的地方。整个逻辑离散化映射到1、add和query循环条件idx n和idx 0都依赖于下标从1开始。如果在离散化时映射到了0或者在query(x-1)时x可能为1此时x-10query(0)会直接返回0逻辑上没错但必须确保add操作不会传入0。一个健壮的写法是在离散化后可以检查一下最小值是否为1或者在任何可能传入0的地方进行判断。5.4 与归并排序解法的对比选择虽然两者时间复杂度相同但常数上有差异。树状数组涉及离散化排序、去重、二分查找和多次 log n 操作常数比归并排序略大。但在内存访问模式上树状数组的连续更新/查询可能对缓存更友好。对于纯粹的逆序对问题两者均可。选择树状数组的理由更在于其“可扩展性”在线查询归并排序是离线的必须拿到所有数据后才能计算。树状数组可以支持数据流式输入每来一个数就能知道当前逆序对总数从后往前遍历的思路需要调整。支持修改如果题目要求支持修改某个位置的值并重新查询逆序数归并排序需要全部重算 O(n log n)。而树状数组可以模拟这个过程先减去原值的影响再增加新值的影响每次修改 O(log n)。更高维度对于二维偏序问题如“求满足x_i x_j且y_i y_j的点对”可以通过对一维排序另一维用树状数组维护来解决这是归并排序难以直接处理的。5.5 一个完整的、带注释的鲁棒模板结合以上所有点这里给出一个我更倾向于在竞赛或面试中使用的版本它包含了防御性检查和一些习惯写法。#include vector #include algorithm using namespace std; class Fenwick { vectorint bit; int n; public: Fenwick(int n) : n(n), bit(n 1, 0) {} void add(int idx, int delta) { // 习惯用 while (idx n) 而不是 idx bit.size()更清晰 for (; idx n; idx idx -idx) bit[idx] delta; } int sum(int idx) { int s 0; for (; idx 0; idx - idx -idx) s bit[idx]; return s; } // 可选查询区间 [l, r] 的和 int rangeSum(int l, int r) { if (l r) return 0; return sum(r) - sum(l - 1); } }; // 离散化函数返回映射后的数组 vectorint discretize(vectorint a) { vectorint b a; sort(b.begin(), b.end()); b.erase(unique(b.begin(), b.end()), b.end()); vectorint res(a.size()); for (int i 0; i a.size(); i) { // lower_bound 返回的是迭代器相减得到下标1 映射到 [1, m] res[i] lower_bound(b.begin(), b.end(), a[i]) - b.begin() 1; } return res; } long long countInversions(vectorint nums) { if (nums.size() 2) return 0; // 边界情况 vectorint arr discretize(nums); int maxVal *max_element(arr.begin(), arr.end()); Fenwick ft(maxVal); long long ans 0; // 从后往前遍历 for (int i (int)arr.size() - 1; i 0; --i) { ans ft.sum(arr[i] - 1); // 查询小于当前值的数量 ft.add(arr[i], 1); // 插入当前值 } return ans; }这个模板清晰、模块化并且将树状数组封装成类方便复用。discretize函数返回新的数组不破坏输入这也是一个良好的实践。掌握这个模板你收获的不仅仅是一个求逆序数的工具更是一种利用高效数据结构维护动态前缀和来解决统计问题的通用思维。下次遇到类似“动态排名”、“实时统计小于某值的个数”这些问题时不妨先想想是不是可以请出树状数组这位老朋友。