0Pricing
Coding Interview Prep · 课时

使用 BIT 计算逆序对

高效统计次序颠倒的元素对

使用 BIT 计算逆序对 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。

什么是逆序对

逆序对是满足 i < j 且 a[i] > a[j] 的一对元素。它表示一对顺序错误的元素，统计逆序对可以衡量数组的无序程度。

逆序对为何重要

逆序对数量等于冒泡 sort会执行的交换次数。竞赛题常常将它隐藏在排名和无序程度相关的问题中。

朴素计数太慢

检查每一对元素需要 O(n^2) 的时间。当 n 约为 100000 时，这意味着一百亿次检查，远远超过时间限制。我们需要更聪明的方法。🐢

BIT 的思路

从左到右扫描，并询问：当前元素之前有多少个元素比它大？树状数组可以在扫描过程中回答这个问题。

按频率计数

BIT 保存的是关于各个数值的频率表。更新(v, 1)表示在当前扫描过程中，值 v 已经出现过。

update(v, 1)

更大意味着后缀

之前比 v 大的值，等于已经看到的元素数量减去不大于 v 的元素数量。对于第 i 个元素，这就是i 减去查询(v)。

inv += i - query(v)

坐标压缩

如果数值很大或为负数，请先将它们映射到 1..n 的排名。这种压缩可以在不改变顺序的情况下缩小 BIT。

rank = {v: i for i, v in enumerate(sorted(set(a)), 1)}

完整扫描过程

遍历数组，将每个元素对应的更大值数量加入总数，然后插入当前值。不断累积的总数就是逆序对数量。

for i, v in enumerate(a):
    inv += i - query(rank[v])
    update(rank[v], 1)

运行时间为 n log n

每个元素都会触发一次查询和一次更新，两者的时间复杂度都是 O(log n)。因此整个计数过程可以在O(n log n)时间内完成。🚀

归并排序是近亲

归并排序也能在合并步骤中以 O(n log n) 的时间统计逆序对。在时间紧张时，BIT 版本通常更简短。

注意计数溢出

逆序对数量最多可以达到约 n 的平方除以二，这是一个很大的数。Python 的整数没有上限，但在其他语言中需要使用64 位类型。

快速检查

请检验您对扫描过程开销的掌握程度。

回顾：统计无序程度

您通过从左到右扫描，并向 BIT 询问之前出现了多少个更大的值，在 O(n log n) 时间内统计出了逆序对。必要时请先压缩数值。✅

常见问题解答

「使用 BIT 计算逆序对」课时是免费的吗？

是的 — 「使用 BIT 计算逆序对」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。

「使用 BIT 计算逆序对」这节课中我会学到什么？

高效统计次序颠倒的元素对 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Coding Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。

「使用 BIT 计算逆序对」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Coding Interview Prep 课中编写并运行代码吗？

能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

  1. 用于前缀和的树状数组
  2. 使用 BIT 计算逆序对
  3. 线段树：构建与查询
  4. 区间更新的延迟传播
← 返回 Coding Interview Prep