怎么用 vector 构建一维前缀和数组
前缀和本质是空间换时间：把每次区间求和的 O(n) 降到 O(1)，代价是多开一个长度为 n+1 的数组。关键不是“怎么算”，而是“下标怎么对齐”。
- 原始数组
a[0..n-1]，前缀和数组prefix[0..n]，其中prefix[0] = 0，prefix[i] = a[0] + a[1] + ... + a[i-1] - 这样设计后，
[l, r]（闭区间，0-indexed）的和就是prefix[r+1] - prefix[l]，不用手调边界 - 常见错误：把
prefix开成n长，或让prefix[0] = a[0]，结果查[0,0]时要么越界要么漏项
示例：
vector<int> a = {1, 2, 3, 4};
vector<int> prefix(a.size() + 1, 0);
for (int i = 0; i < a.size(); i++) {
prefix[i + 1] = prefix[i] + a[i];
}
// prefix = {0,1,3,6,10} → [1,2] 和 = prefix[3] - prefix[1] = 6 - 1 = 5
二维前缀和的 getSum 怎么写才不出错
二维前缀和容易在容斥原理上翻车——不是公式记错，是坐标映射混乱。核心是统一用“左上角为 (0,0)、右下角为 (i,j) 的矩形和”定义 prefix[i+1][j+1]。
-
prefix[i+1][j+1] = prefix[i][j+1] + prefix[i+1][j] - prefix[i][j] + a[i][j]，注意所有下标都比原数组大 1 - 查矩形
[r1, c1]到[r2, c2]（闭区间）：结果是prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1] - 典型坑：
r1或c1为 0 时，prefix[r1][*]是合法的（因为prefix行列都多开了一行一列），但若误写成prefix[r1-1]就直接越界
修改单点值后还能用前缀和吗？
不能直接用。前缀和是静态结构，一旦 a[i] 改变，从 i 往后的所有 prefix[j]（j > i）全失效。暴力重算整个 prefix 是 O(n)，和不用前缀和没区别。
立即学习“C++免费学习笔记（深入）”；
- 如果需要频繁单点修改 + 区间查询，改用
fenwick tree（树状数组）或segment tree（线段树） - 真要硬上前缀和，只能接受“修改 O(n)，查询 O(1)”的不对称代价，且必须重新跑一遍前缀和构建循环
- 工程中常见误判：以为加个
update(i, delta)函数就能“动态维护”，实际只是把错误延迟到查询时暴露
long long 溢出和初始化陷阱
前缀和本身不复杂，但溢出和初始化错位会让结果静默错误——查出来数不对，但编译运行都正常。
- 如果
a元素最大1e5，长度1e5，前缀和最大可能到1e10，int直接溢出，必须用long long -
prefix初始化必须全为 0，尤其用vector<long long>(n+1)</long>时，C++ 默认零初始化，但若写成vector<long long> prefix(n+1, 0LL)</long>更明确 - 调试技巧：打印
prefix[0]和prefix[1]，确认是否等于 0 和a[0]，能快速排除初始化/下标偏移问题
真正卡住人的从来不是公式，是第 0 个元素要不要包含、下标该不该 +1、数据类型够不够宽——这些细节错一个，整个区间结果就偏掉，而且很难一眼看出来。
