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

前缀和题解多加一个哨兵少掉一堆边界判断一、前缀和不是只会套公式前缀和是区间问题里的基础工具。很多题解会直接写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) 区间查询。实现时建议使用哨兵和半开区间减少边界判断。遇到子数组和类问题要把公式转成哈希查询。模板不难难的是边界、更新场景和数值范围别写错。