前缀和：入门
Source: Dev.to
如果你曾经看到一道编程挑战时感觉像是面对一堵砖墙，你并不孤单。大多数情况下，关键并不是要成为数学天才，而是要识别模式。
在本系列中，我们会从入门到专家级别拆解最核心的编程模式——保持简洁、实用，并（希望）带点乐趣。
今天我们深入探讨前缀和（Prefix Sum）。
无论你是为一次重要面试做准备，还是仅仅想写出更简洁、更高效的代码，掌握这个模式都将彻底改变游戏规则。
让我们抛开术语，看看它到底是怎么工作的！
什么是前缀和？
想象一下，你站在一条漫长道路的起点上，每走一英里，就有一个标志告诉你在那个特定地点地下埋了多少枚硬币。
如果我问：“第 3 英里到第 8 英里之间有多少枚硬币？”，你通常需要从 3 走到 8 ，一枚一枚地把它们加起来。
这对短距离的步行来说还算可行，但如果道路长达 10 000 英里，而我向你提出 1 000 个不同的问题呢？你会筋疲力尽！
前缀和 是一种预处理技术，它为数组创建一个“累计总和”。只需在前期做一点工作，就能在 O(1) 时间内回答任何“区间求和”查询——把重复的加法任务转化为一次简单的减法。
数学逻辑
我们创建一个新数组（称为 prefix），其中每个索引 i 处的元素存储原始数组 arr 从开头到该索引的所有元素之和。
公式
prefix[i] = arr[0] + arr[1] + … + arr[i]更高效的递推
prefix[i] = prefix[i‑1] + arr[i] (for i > 0)一个简单的例子
arr = [3, 1, 4, 1, 5]
Index 0: 3
Index 1: 3 + 1 = 4
Index 2: 4 + 4 = 8
Index 3: 8 + 1 = 9
Index 4: 9 + 5 = 14
prefix = [3, 4, 8, 9, 14]要获取 索引 2 到 4（4, 1, 5）之间元素的和：
result = prefix[4] – prefix[1] = 14 – 4 = 10为什么这样可行：
prefix[4] = A0 + A1 + A2 + A3 + A4
prefix[1] = A0 + A1
=> prefix[4] – prefix[1] = A2 + A3 + A4效率与复杂度
时间复杂度
无 前缀和：每个区间查询耗时 O(N)，因此 M 次查询耗时 O(M × N)。
有 前缀和：构建 prefix 数组一次性耗时 O(N)；每次查询耗时 O(1)。
空间复杂度
我们通常会额外分配一个大小为 N 的数组，空间复杂度为 O(N)。
如果直接覆盖原数组，则可以实现 O(1) 的额外空间。
如果你需要快速回顾一下 Big‑O 符号的概念，请查看我之前的指南 此处。
它在哪里使用？（应用）
- 金融与销售分析 – 对任何自定义日期范围即时求和。
- 图像处理 – 2‑D 前缀和（累计面积表）实现对模糊、特征检测等的矩形求和常数时间计算。
- 网络分析 – 对时间序列数据的累计访客或活跃用户。
- 数据库查询优化 – 加速范围扫描和聚合查询。
- 游戏开发 – 累计分数、资源或 2‑D 光照/阴影计算。
经典面试题
- Range Sum Query – 反复求两个索引之间的和。
- Pivot Index – 找到一个索引，使左侧元素之和等于右侧元素之和。
- Subarray Sum Equals K – 结合前缀和与哈希表来统计和为
K的子数组。 - Maximum Subarray (Kadane’s variant) – 使用前缀和计算前缀的最小值/最大值。
提前识别这些模式可以在面试中为你节省大量时间和压力。
Source: …
实现
现在，让我们看看这个模式是如何实际运作的！
在这些演示中，我将使用 C#。不过，如果你平时使用 Python、Java、JavaScript 等语言，也不要受限于语言选择。逻辑和底层模式在所有语言中都是完全相同的——只有语法不同。欢迎跟随示例，用你喜欢的语言实现相同的逻辑。
using System;
public class PrefixSumExample
{
public static void Main()
{
int[] nums = { 3, 1, 4, 1, 5 };
// 预处理：构建前缀和数组
int[] prefixSum = BuildPrefixSum(nums);
// 查询：获取区间 [索引 1 到 3] 的和（值为：1, 4, 1）
// 期望结果：6
int result = GetRangeSum(prefixSum, 1, 3);
Console.WriteLine("\nSum of range [1 to 3]: " + result);
}
public static int[] BuildPrefixSum(int[] A)
{
int n = A.Length;
int[] P = new int[n];
// 第一个元素始终相同
P[0] = A[0];
for (int i = 1; i // Incomplete loop shown as in the original source
}
}如果卡住了也不要气馁！目标不是在五分钟内解决每个问题，而是 识别模式。祝编码愉快！
保持联系
通过以下渠道关注我，获取最新的洞见和教程：
如有任何咨询、游戏或问题，欢迎通过 email: 与我联系！我随时为你解答任何疑问。
不要错过未来的文章和开发技巧！