前缀和题解：多加一个哨兵，少掉一堆边界判断

前缀和题解：多加一个哨兵，少掉一堆边界判断

一、前缀和不是只会套公式

前缀和是区间问题里的基础工具。很多题解会直接写sum[r] - sum[l - 1]。这个公式没错，但实现时边界容易出问题。尤其是 l 为 0 或 1 时，代码要么多写 if，要么数组越界。

更稳定的写法是加一个哨兵。令prefix[0] = 0，前 i 个元素的和放在prefix[i]。这样区间[l, r)的和就是prefix[r] - prefix[l]。边界清楚，代码也更干净。

二、前缀和本质是把重复累加变成差分查询

前缀和适合多次查询静态数组区间和。预处理一次，查询 O(1)。

flowchart TD A[原数组] --> B[构建 prefix] B --> C[查询区间 l 到 r] C --> D[prefix[r] - prefix[l]] D --> E[返回区间和]

如果数组频繁修改，普通前缀和就不适合了，要考虑树状数组或线段树。

三、用半开区间减少边界噪音

下面是 Python 示例。半开区间[l, r)和语言切片习惯一致。

def build_prefix(nums: list[int]) -> list[int]: prefix = [0] for x in nums: prefix.append(prefix[-1] + x) return prefix def range_sum(prefix: list[int], left: int, right: int) -> int: if not (0 <= left <= right < len(prefix)): raise ValueError("invalid range") return prefix[right] - prefix[left]

right < len(prefix)是因为 prefix 长度比原数组多 1。查询原数组[0, n)时，right 可以等于 n。

四、前缀和常和哈希表一起出现

子数组和为 K 这类题，不是只查固定区间，而是找有多少历史前缀满足prefix[j] - prefix[i] = k。变形后就是查prefix[i] = prefix[j] - k。

这时哈希表保存历史前缀出现次数。注意先查再加当前前缀，否则空区间或当前项会被错误计入。

最后，前缀和可能溢出。Java、C++ 里数据范围大时要用 long。复杂度写 O(n) 之前，先确认数值类型扛得住。

二维前缀和也是同一思想，只是容斥更容易写错。矩形(r1,c1)到(r2,c2)的和，要加左上角被减掉两次的区域。写题解时不要只给公式，最好画出四块区域，否则读者很容易把加减号背反。

差分数组和前缀和是反向思路。区间多次修改、最后一次查询时，用差分更合适；多次查询、数组静态时，用前缀和更合适。选错工具，复杂度会直接变形。

最后，前缀和题要明确下标语义。题目给的是 1-based 还是 0-based，代码内部用半开还是闭区间，都要在开头写清楚。边界错误通常不是因为不会算法，而是下标协议没统一。

如果题目包含负数，前缀和依然可用，但双指针未必可用。很多子数组问题因为出现负数，窗口和不再单调，滑动窗口会失效。题解里要把这个区别讲清楚，否则读者会把两个模板混着用。

前缀和还可以用于异或。区间异或同样能用prefix[r] ^ prefix[l]，因为相同值异或会抵消。把“可逆运算”这个性质讲出来，读者就能迁移到更多题，而不是只记求和。

五、总结

前缀和的核心是用预处理换 O(1) 区间查询。实现时建议使用哨兵和半开区间，减少边界判断。遇到子数组和类问题，要把公式转成哈希查询。模板不难，难的是边界、更新场景和数值范围别写错。