cpp中的前缀和 后缀和

前缀和、后缀和是数组预处理技巧，作用是用O(n)预处理，实现O(1)快速查询区间和
一、一维前缀和

include

using namespace std;

int main() {
vector arr = {1, 2, 3, 4}; // 原数组
int n = arr.size();

// 1. 定义前缀和数组（必须用long long，防止溢出）
vector<long long> preSum(n + 1, 0); // 2. 预处理：O(n)时间
for (int i = 1; i <= n; ++i) {preSum[i] = preSum[i - 1] + arr[i - 1];
}// 3. O(1)查询：原数组 闭区间[l, r] 的和（0<=l<=r<n）
int l = 1, r = 2;
long long sum = preSum[r + 1] - preSum[l]; // 结果：2+3=5
return 0;

}
原数组 [l, r] 区间和 = preSum[r+1] - preSum[l]
典型应用场景

1. 多次查询任意子数组的和
2. 统计「和为k的子数组数量」
3. 寻找「左右两边和相等的数组分割点」
4. 辅助解决最大子数组和、子数组平均值问题

二、一维后缀和

include

using namespace std;

int main() {
vector arr = {1, 2, 3, 4};
int n = arr.size();

// 1. 定义后缀和数组（long long防溢出）
vector<long long> sufSum(n + 1, 0); // 2. 预处理：倒序遍历，O(n)时间
for (int i = n - 1; i >= 0; --i) {sufSum[i] = sufSum[i + 1] + arr[i];
}// 3. O(1)查询：原数组 [i, n-1] 后缀区间和
int i = 1;
long long sum = sufSum[i]; // 结果：2+3+4=9
return 0;

}
原数组 [i, 末尾] 区间和 = sufSum[i]
典型应用场景

1. 快速求数组右侧所有元素的和
2. 结合前缀和，判断「数组平衡点」（左边和=右边和）
3. 倒序区间查询、双指针优化

二维前缀和

1. 定义：preSum[i][j] 表示左上角(0,0)到(i-1,j-1)的矩阵和
2. 公式：子矩阵(x1,y1)到(x2,y2)的和 =
   preSum[x2+1][y2+1] - preSum[x1][y2+1] - preSum[x2+1][y1] + preSum[x1][y1]

注意事项

1. 下标处理
   前缀和数组长度 = 原数组长度 + 1，preSum[0] 必须初始化为0
   原数组是0基，前缀和是1基：
   后缀和必须倒序遍历（从n-1到0），sufSum[n] = 0
2. 数据溢出
   int类型最多存约2e9，数组累加极易超出范围：
   强制用 long long 定义前缀和/后缀和数组，不用int
3. 静态数组限制
   前缀和/后缀和是静态预处理：
   原数组修改后，必须重新计算前缀/后缀和
   若数组频繁修改，不要用前缀和
4. 边界条件
   空数组：n=0时，提前判断，避免循环越界
   单元素数组：公式依然生效（l=r=0，和为arr[0]）