0Pricing
Competitive Programming Academy · 课时

用于前缀和的树状数组

在 log n 时间内执行单点更新和前缀查询

用于前缀和的树状数组 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。

前缀数组为何失效

普通前缀和数组可以即时回答区间问题，但一次更新就会迫使您重新构建它。更新次数很多时，这会变得很慢。⏱️

认识树状数组

树状数组，也就是 BIT，同时支持单点更新和前缀查询，时间复杂度均为 O(log n)。它是处理动态累计总和的首选工具。

从设计上采用一位索引

树状数组存储在一位索引数组中。我们将索引 0 作为无实际含义的哨兵，因此所有真实数据都从位置 1开始。

tree = [0] * (n + 1)

最低有效位的妙用

每个索引都覆盖一段数值。该区块的大小等于i & -i，也就是 i 的最低有效位。这一技巧支撑了整棵树的运行。

lowbit = i & -i

更新单个位置

要在位置 i 加上一个值，请在每一步通过最低有效位向前跳转，访问所有包含 i 的区块。

while i <= n:
    tree[i] += delta
    i += i & -i

查询前缀和

要计算前 i 个值的总和，请向后遍历，每一步减去最低有效位，直到到达零。

s = 0
while i > 0:
    s += tree[i]
    i -= i & -i

两个循环都是对数级

每个循环每次迭代都会关闭一个比特位，因此最多运行log n次。这就是更新和查询都能保持高效的原因。

用两个前缀和求区间和

想求从 l 到 r 的总和吗？计算prefix(r) 减去 prefix(l-1)即可，就像使用静态前缀数组一样，只是现在更新也很廉价。

range_sum = query(r) - query(l - 1)

构建树状数组

最简单的构建方式是对每个初始值调用更新。这样需要 O(n log n) 的时间，对于大多数竞赛来说已经足够快。

for i, v in enumerate(a, 1):
    update(i, v)

极小的内存占用

树状数组只需要一个大小为 n+1 的数组。这种紧凑的内存占用也是它深受竞赛选手喜爱的原因之一。💾

何时使用 BIT

如果需要交替执行单点更新以及前缀和或区间和查询，请选择树状数组。它代码简短，而且很难被其他方案超越。

快速检查

让我们巩固一下循环的移动方式。

回顾：BIT 基础

您认识了树状数组：采用一位索引，由 i & -i 驱动，单点更新和前缀查询的时间复杂度均为 O(log n)。接下来，我们将使用它统计逆序对。🎯

常见问题解答

「用于前缀和的树状数组」课时是免费的吗？

是的 — 「用于前缀和的树状数组」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。

「用于前缀和的树状数组」这节课中我会学到什么？

在 log n 时间内执行单点更新和前缀查询 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Competitive Programming Academy 需要有经验吗？

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

「用于前缀和的树状数组」课时需要多长时间？

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

我能在这节 Competitive Programming Academy 课中编写并运行代码吗？

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

此课程中的所有课时

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