一、从刚落幕的国际信息学奥林匹克说起2026 年 8 月 9 日至 15 日第 38 届国际信息学奥林匹克竞赛在乌兹别克斯坦首都塔什干举行来自全球 90 多个国家和地区的近 400 名选手同场竞技。中国队四名选手斩获 3 金 1 银、团体总分第一其中一位选手以 498.27 分成为本届最高分。截至本届中国队累计金牌已突破 100 枚。值得注意的是官方对赛题范围的描述算法设计、数据结构与程序设计实现。数据结构被单独拎出来不是偶然——在真实赛场上同一道题用暴力和用合适的数据结构往往就是 0 分和满分的差别。今天要讲的树状数组Binary Indexed Tree也叫 Fenwick Tree就是这样一件性价比极高的兵器代码只有十来行却能把很多 $O(n^2)$ 的统计问题压到 $O(n \log n)$。我们用一道原创题把它彻底讲透。二、原创练习题科技节机器人列队题目描述学校科技节要举办机器人巡游表演。$n$ 台机器人排成一列从左到右第 $i$ 台的高度为 $a_i$。导演希望它们按高度从矮到高非递减排列这样队形看起来最整齐。由于场地狭窄机器人只能与相邻的那一台交换位置每交换一次记为一步。请回答三个问题问题 A有多少组高度倒置的机器人即满足 $i j$ 且 $a_i a_j$ 的下标对 $(i, j)$ 有多少个。问题 B最少需要多少步相邻交换才能让整列机器人变成非递减排列问题 C对每一台机器人输出它左边比它高的机器人数量。输入格式第一行一个整数 $n$。第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$。输出格式第一行输出问题 A 的答案问题 B 的答案与它相同原因见后文。第二行输出 $n$ 个整数为问题 C 的答案。数据范围$0 \le n \le 5 \times 10^5$$-10^9 \le a_i \le 10^9$高度可能重复。样例输入8 5 3 9 3 7 1 9 2样例输出15 0 1 0 2 1 5 0 6样例解释以第 8 台高度 2为例它左边有 5、3、9、3、7、9 共 6 台比它高所以第 8 个数是 6。把 8 个位置的贡献相加$01021506 15$恰好等于逆序对总数 15。这个分解求和的关系是本题的核心线索。三、核心考点拆解这道题看似只是数数实际串起了五个高频考点。考点 1逆序对的定义与相邻交换的等价性问题 A 求的就是标准的逆序对数量。问题 B 为什么答案完全一样关键观察交换相邻两个元素逆序对数量最多变化 1。若 $a_i \le a_{i1}$交换后它们变成一个新的逆序对总数 $1$若 $a_i a_{i1}$交换后这一对被消掉总数 $-1$而对于其他任意一对元素 $(x, y)$交换相邻位置并不改变它们的前后相对次序所以贡献不变。排好序的数组逆序对为 0。每一步最多消掉 1 个逆序对所以至少需要逆序对个数步而冒泡排序恰好每次交换都消掉 1 个能达到这个下界。结论最少相邻交换次数 逆序对个数这是一个必须记住的经典结论。顺带一提如果允许任意两个位置交换答案就完全不同了见进阶三别混为一谈。考点 2为什么必须离散化树状数组是以值为下标的桶。本题 $a_i$ 可以到 $10^9$开这么大的数组直接爆内存。离散化就是把值域压缩到 $1 \dots m$$m \le n$ 为不同值的个数只保留大小关系复制一份数组排序去重用二分查找lower_bound/bisect_left把每个原值换成它在去重数组里的排名 $1$转成 1-based。排名保持了原有的大小顺序因此所有比较结果不变。这一步同时顺手解决了负数和小数先转排名即可的问题。考点 3树状数组的两个动作树状数组只做两件事都靠lowbit(i) i (-i)驱动add(i, v) : 把位置 i 的值加上 v —— 沿 i lowbit(i) 往上跳 query(i) : 返回前缀和 [1..i] —— 沿 i - lowbit(i) 往下跳tree[i]管理的是区间 $(i - \text{lowbit}(i),\ i]$。两个操作跳的次数都不超过 $\log n$所以单次都是 $O(\log n)$。在本题里我们用它维护一个计数桶add(r, 1)表示排名 $r$ 的高度出现了一次query(r)表示目前已插入的元素中排名 $\le r$ 的有多少个。考点 4扫描方向决定统计口径同一个树状数组扫描方向不同含义完全不同。这是最容易写错的地方。目标扫描方向查询写法含义问题 A / B逆序对总数从右往左query(r - 1)右侧严格小于$a_i$ 的个数问题 C左边比它高的个数从左往右i - query(r)已插入 $i$ 个减去 $\le a_i$ 的个数注意问题 A 用query(r - 1)而不是query(r)逆序对要求严格大于相等的高度不算倒置必须把等于 $a_i$ 的那一档排除掉。这个差一是本题最高频的错误来源。考点 5答案的量级$n 5 \times 10^5$ 且完全逆序时逆序对数为 $\frac{n(n-1)}{2} \approx 1.25 \times 10^{11}$早已超过 32 位int上限 $2147483647$。必须用long longPython 无此顾虑。这是本题最经典的隐形丢分点。四、解法一树状数组 离散化主解思路一句话从右往左扫每遇到一个元素先问右边已经放进去了多少个比我矮的再把自己放进桶里。C 实现#include cstdio #include vector #include algorithm using namespace std; int m; // 离散化后的值域大小 vectorint tree_; // 树状数组有效下标 1..m void add(int i, int v) { // 单点加 for (; i m; i i (-i)) tree_[i] v; } int query(int i) { // 前缀和 [1..i] int s 0; for (; i 0; i - i (-i)) s tree_[i]; return s; } int main() { int n; if (scanf(%d, n) ! 1) return 0; vectorint a(n); for (int i 0; i n; i) scanf(%d, a[i]); // ---- 离散化把任意大小的高度压到 1..m ---- vectorint s(a); sort(s.begin(), s.end()); s.erase(unique(s.begin(), s.end()), s.end()); m (int)s.size(); tree_.assign(m 1, 0); // ---- 问题 A / B从右往左统计逆序对 ---- long long ans 0; // 必须 long long for (int i n - 1; i 0; --i) { int r int(lower_bound(s.begin(), s.end(), a[i]) - s.begin()) 1; ans query(r - 1); // 右侧严格小于 a[i] 的个数 add(r, 1); } printf(%lld\n, ans); // ---- 问题 C清空后从左往右 ---- tree_.assign(m 1, 0); for (int i 0; i n; i) { int r int(lower_bound(s.begin(), s.end(), a[i]) - s.begin()) 1; printf(%d%c, i - query(r), i 1 n ? \n : ); add(r, 1); } return 0; }Python 实现import sys from bisect import bisect_left def main(): data sys.stdin.read().split() if not data: return n int(data[0]) a list(map(int, data[1:1 n])) # ---- 离散化 ---- s sorted(set(a)) m len(s) tree [0] * (m 1) def add(i): while i m: tree[i] 1 i i (-i) def query(i): t 0 while i 0: t tree[i] i - i (-i) return t # ---- 问题 A / B从右往左 ---- ans 0 for x in reversed(a): r bisect_left(s, x) 1 ans query(r - 1) # 严格小于所以是 r-1 add(r) print(ans) # ---- 问题 C清空后从左往右 ---- tree [0] * (m 1) res [] for idx, x in enumerate(a): r bisect_left(s, x) 1 res.append(idx - query(r)) # 已插入 idx 个减去 x 的 add(r) print( .join(map(str, res))) main()两份代码对样例均输出15 0 1 0 2 1 5 0 6五、解法二归并排序求逆序对对拍神器逆序对还有一条完全不同的路在归并排序合并两个有序段时顺手计数。当左段L[i] R[j]说明R[j]比左段剩下的L[i..]全部都小一次性累加len(L) - i个逆序对。def count_inversions(a): def rec(arr): if len(arr) 1: return arr, 0 mid len(arr) // 2 L, c1 rec(arr[:mid]) R, c2 rec(arr[mid:]) out, i, j, c [], 0, 0, c1 c2 while i len(L) and j len(R): if L[i] R[j]: # 注意是 相等不算逆序对 out.append(L[i]); i 1 else: out.append(R[j]); j 1 c len(L) - i # 关键一行 out.extend(L[i:]); out.extend(R[j:]) return out, c return rec(list(a))[1]两种解法的取舍树状数组归并排序代码量稍多含离散化稍少是否需要离散化需要不需要能否顺带回答问题 C能换扫描方向不方便可扩展性强区间查询、第 k 小、二维偏序弱专用于逆序对常数小递归开销略大建议赛场上写树状数组做主解写归并排序做对拍验证。两条思路互相独立一旦答案不一致必有一方写错比盯着代码看要高效得多。六、复杂度分析树状数组解法时间离散化排序 $O(n \log n)$ $n$ 次add/query各 $O(\log n)$共 $O(n \log n)$。空间原数组 离散化数组 树状数组共 $O(n)$。归并排序解法时间 $O(n \log n)$空间 $O(n)$递归栈 $O(\log n)$合并临时数组 $O(n)$。暴力枚举$O(n^2)$。在 $n 5 \times 10^5$ 时约 $1.25 \times 10^{11}$ 次比较必然超时但它是最好的对拍基准$n \le 2000$ 时可以放心用。七、易错点清单写这道题最容易踩的七个坑逐条对照检查答案用了int。$1.25 \times 10^{11}$ 远超int上限必须long long。这是本题第一大丢分点。把query(r - 1)误写成query(r)。逆序对要求严格大于相等的高度不能算必须用r - 1把等于 $a_i$ 的那一档排除掉写成r会在有重复元素时多算一批。树状数组下标从 0 开始。lowbit(0) 0add(0, 1)会陷入死循环。离散化后的排名必须1变成 1-based。两次统计之间忘记清空树状数组。问题 A 和问题 C 共用一棵树中间必须assign(m 1, 0)重置否则问题 C 的结果会掺进问题 A 的残留计数。离散化忘记去重。不去重会让 $m$ 变成 $n$虽然一般不至于出错但相等元素的排名不唯一lower_bound的语义会变得混乱容易连带写错第 2 条。归并排序里写成L[i] R[j]。必须是否则相等元素会被误算成逆序对。$n 0$ 未处理。空输入时循环不执行、输出空行即可但要保证tree_大小至少为 1sort/unique对空 vector 也要安全。八、四个进阶方向进阶一树状数组倍增求第 k 小树状数组不只能算前缀和还能在 $O(\log n)$ 内直接定位第 k 小的值比二分套 query的 $O(\log^2 n)$ 更快。原理是从最高位往低位试着往右跳能跳就跳、并把已经越过的计数从 $k$ 里扣掉int LOG; // 满足 (1LOG) m 的最大值 int kth(int k) { // 返回第 k 小的排名下标1..m int pos 0; for (int j LOG; j 0; --j) { int nxt pos (1 j); if (nxt m tree_[nxt] k) { pos nxt; k - tree_[nxt]; } } return pos 1; }配合add(r, 1)/add(r, -1)就能维护一个支持插入、删除、查询第 k 小的动态排名集合——这是权值树状数组的标准玩法很多动态中位数滑动窗口第 k 大的题都靠它。进阶二逆序对奇偶性与数字华容道逆序对的奇偶性是一个排列的不变量任意一次相邻交换都会让它 $\pm 1$也就是奇偶性翻转一次。这条性质能直接判定经典的 15 数码数字华容道是否可解把空格看作最大数计算整个排列的逆序对奇偶性再结合空格所在行号就能在不搜索的情况下断定目标状态可达与否。判定只需 $O(n^2)$ 或 $O(n \log n)$比盲目跑 BFS 省下天量时间。进阶三换成任意交换答案完全不同如果放开限制允许交换任意两个位置元素互不相同最少交换次数变成$$\text{答案} n - (\text{置换环的个数})$$做法是把当前位置 → 排序后该元素应在的位置看成一个置换找出所有环每个长度为 $L$ 的环需要 $L - 1$ 次交换。对比一下差别有多大数组[3, 2, 1]的逆序对是3相邻交换要 3 步但任意交换只需1步直接换 3 和 1。读题时务必看清是相邻交换还是任意交换这是同类题最常见的陷阱设置。进阶四从单点修改升级到区间修改区间查询原始树状数组是单点改 前缀查。用两棵树状数组 $B_1$、$B_2$ 配合差分就能支持区间加 区间求和区间 $[l, r]$ 加 $v$在 $B_1$ 上做add(l, v)、add(r1, -v)在 $B_2$ 上做add(l, v*(l-1))、add(r1, -v*r)。前缀和 $[1, i]$ 查询$i \times \text{query}{B_1}(i) - \text{query}{B_2}(i)$。这样一来很多必须上线段树的题目就能用两个十行函数解决代码短、常数小、调试快。如果还要处理区间内逆序对个数这类问题再往上就是莫队算法或树套树可以作为下一阶段的目标。九、小结与互动回顾一下这道题给出的完整链条问题转化把最少相邻交换次数识别为逆序对计数考点 1 的等价性证明离散化把 $10^9$ 的值域压到 $O(n)$让以值为下标成为可能树状数组用lowbit两个方向的跳跃$O(\log n)$ 完成单点加与前缀和扫描方向右→左统计逆序对左→右统计前缀贡献同一份数据结构两种口径对拍验证归并排序 暴力枚举双重兜底避免差一和溢出这类沉默错误。本文所有代码在发布前都做过验证Python 的树状数组、归并排序、暴力三套解法在 3000 组随机数据含空数组、全相等、完全逆序、含负数、大值域等边界上答案完全一致C 版与 Python 版对样例输出逐字符相同进阶一的倍增求第 k 小在 2000 组随机计数分布上与暴力扫描一致进阶三的置换环公式与小规模 BFS 最短交换次数一致。留几个问题给你动手如果题目改成求满足 $i j$ 且 $a_i 2 \times a_j$ 的对数树状数组的写法要怎么改提示查询边界不再是 $r-1$需要另做一次二分问题 C 若改成右边比它矮的个数扫描方向和查询式子各是什么试着把进阶四的两棵树状数组写出来用随机数据和暴力前缀和对拍看能不能一次通过。如果这篇讲解帮你理清了树状数组的思路欢迎点赞收藏对哪个考点还有疑问评论区留言下一篇挑最多人问的展开细讲。下一篇预告倍增思想的另一大应用——树上最近公共祖先LCA以及它如何把树上路径查询降到 $O(\log n)$。 免费少儿编程资料夸克网盘领取以下资料来自夸克网盘分享点击链接可直接保存若需在 App 内打开也可复制下方明文链接全国青少年信息素养大赛复赛集训题目PythonC.docxhttps://pan.quark.cn/s/93995d3cb1502024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdfhttps://pan.quark.cn/s/da97b5dbf75dPython背记手册.pdfhttps://pan.quark.cn/s/7568ae9ca92bPython课程https://pan.quark.cn/s/a94bf02d00c62024信息素养大赛图形化复赛集训题答案3-9https://pan.quark.cn/s/6ccab7ec3cbc2025年03月份电子学会考级真题https://pan.quark.cn/s/4403c42289122025全国青少年信息素养大赛赛项说明https://pan.quark.cn/s/d9d0df4a9f29青少儿信息素养大赛编程资料https://pan.quark.cn/s/4ab6bd83be8a资料持续更新关注获取最新分享。