前缀和是手动构造的辅助数组，用于将多次区间求和查询从o(n)降至o(1)，适用于静态或低频修改数组；其定义为prefix[0]=0，prefix[i]为前i个元素之和，区间[l,r]和为prefix[r+1]−prefix[l]。
什么是前缀和？它为什么能加速区间查询
前缀和不是库函数，而是手动构造的辅助数组，核心作用是把多次 sum(l, r) 查询从 O(n) 降到 O(1)。它只适用于「数组不修改」或「修改极少」的场景。一旦原数组频繁变动，就得考虑线段树或树状数组。
构造方式很简单：设原数组为 arr，长度为 n，定义前缀和数组 prefix 满足：prefix[0] = 0，prefix[i] = arr[0] + arr[1] + ... + arr[i-1]（即 prefix[i] 表示前 i 个元素之和）。这样区间 [l, r]（闭区间，0-indexed）的和就是 prefix[r+1] - prefix[l]。
C++ 实现时要注意的索引偏移和边界
最容易出错的是下标对齐——尤其是当题目给的查询是 1-indexed 区间时。C++ 里推荐统一用 0-indexed 原数组 + 1-size 的 prefix 数组，避免越界和减 1 错误。
- 声明：用
vector<long long> prefix(n + 1)</long>，而不是n；prefix[0] = 0必须显式设置 - 构造循环：从
i = 1到n，写成prefix[i] = prefix[i-1] + arr[i-1] - 查区间
[l, r]（0-indexed）：结果是prefix[r+1] - prefix[l]；若输入是 1-indexed 的L, R，直接用prefix[R] - prefix[L-1]
处理负数、大数和溢出风险
前缀和本身不关心元素正负，但累加过程容易溢出。int 通常不够用，尤其当 arr 元素绝对值大或 n > 1e5 时。
- 别默认用
int存prefix，优先选long long - 如果题目保证和在 int 范围内，也要检查中间步骤：比如
prefix[r+1] - prefix[l]可能产生负溢出（虽然少见），稳妥起见仍建议 long long - 不需要对前缀和取模——除非题目明确要求「输出对 MOD 取模的结果」，此时所有加法都要
% MOD，且注意减法后加 MOD 再取模：(prefix[r+1] - prefix[l] + MOD) % MOD
二维前缀和怎么套用同一逻辑
一维是「线性累加」，二维就是「矩形累加」，本质仍是容斥：sum[x2][y2] 表示从 (0,0) 到 (x2,y2) 的子矩阵和。查询任意子矩阵 (r1,c1) 到 (r2,c2)（闭区间）时，公式是：
prefix2d[r2+1][c2+1] - prefix2d[r1][c2+1] - prefix2d[r2+1][c1] + prefix2d[r1][c1]
构造时必须严格按顺序：先外层行循环，再内层列循环，且每步都依赖左、上、左上三个位置：
prefix2d[i][j] = prefix2d[i-1][j] + prefix2d[i][j-1] - prefix2d[i-1][j-1] + matrix[i-1][j-1]- 同样用
vector<vector long>> prefix2d(m + 1, vector<long long>(n + 1))</long></vector>，避免边界特判
多维扩展容易漏掉容斥项或下标错位，第一次手写建议先画 3×3 矩阵手动推一遍 prefix2d[2][2] 怎么算。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
