构建前缀和数组
一次性预计算累计总和
构建前缀和数组 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
重复求和问题
设想一下，要在同一个数组上回答数百个区间求和问题。如果每次都从头计算区间总和，速度会很慢。使用前缀和就能解决这个问题。🚀
什么是前缀和
前缀和数组会在每个索引处存储截至该位置的所有元素总和。一次预计算扫描就能将缓慢的求和变成即时查询。
一个小例子
对于 [3, 1, 4]，累计总和依次为 3、4、8。这个不断增长的总和列表就是前缀和。
核心递推关系
每个元素都等于前一个总和加上当前元素。这个一行就能写出的递推关系是整个技巧的核心。
prefix[i] = prefix[i - 1] + a[i]用代码构建
遍历数组一次，同时维护一个累计总和。每一步都追加新的总和，因此构建该数组只需一次线性扫描。
prefix = [0]
for x in a:
prefix.append(prefix[-1] + x)为什么开头加零有帮助
在 prefix 开头放置一个零，意味着 prefix[i] 保存前 i 个元素的总和。这样之后进行区间计算会更简洁。
索引约定
在开头加入零后，prefix[k] 等于 a[0] + ... + a[k-1]。牢记这一约定可以避免令人头疼的索引偏移错误。
构建成本
构建前缀和数组时，每个元素都恰好被访问一次，因此需要 O(n) 时间。只需付出一次成本，之后就能反复使用。
预计算一次，频繁查询
最大的优势在于这种权衡：先花费一次线性扫描，之后每次求和查询都能变成快速查找，而不必再次循环。
Python 风格的快捷方式
标准库可以替您构建累计总和。itertools.accumulate 通过一次简洁的调用生成累计总和。
from itertools import accumulate
prefix = [0] + list(accumulate(a))注意内存
前缀和数组的长度等于输入长度加一。对于超大输入，请记住它会使您的内存占用翻倍。
快速检查
您正在构建一个前缀和数组。索引 0 通常存放什么？
总结
您已经学会在一次 O(n) 扫描中构建前缀和数组，并通过开头的零实现简洁的索引。预计算一次，之后重复使用。✅
常见问题解答
「构建前缀和数组」课时是免费的吗？
是的 — 「构建前缀和数组」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「构建前缀和数组」这节课中我会学到什么？
一次性预计算累计总和 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「构建前缀和数组」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。