前缀和是一种通过预处理将区间查询复杂度从 O(N) 降至 O(1) 的经典技巧。核心思想是构建一个累加数组,利用递推关系快速计算任意区间的元素和。下面我们从一维到二维,结合具体场景展开讲解。
一维前缀和
假设有一个数组 arr,我们定义 dp[i] 为 [1, i] 区间内所有元素的和。根据定义,dp[i-1] 存储的是 [1, i-1] 的和,因此可以得到递推公式:
dp[i] = dp[i-1] + arr[i]
当需要查询区间 [l, r] 的和时,只需计算 dp[r] - dp[l-1] 即可。
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
vector<int> arr(n + 1);
for (int i = 1; i <= n; i++) cin >> arr[i];
// 使用 long long 防止溢出
vector<long long> dp(n + 1);
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1] + arr[i];
}
while (q--) {
int l, r;
cin >> l >> r;
cout << dp[r] - dp[l - 1] << endl;
}
return 0;
}
二维前缀和
对于矩阵中的区域求和问题,我们可以类比一维情况。为了简化边界处理,通常在矩阵外围添加一行和一列 0。这样,sum[i][j] 表示从 [0, 0] 到 [i, j] 的矩形区域内所有元素的累加和。
递推方程基于容斥原理:当前区域等于上方区域 + 左方区域 - 重叠区域 + 当前点值。
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + matrix[i-1][j-1]
查询左上角 (x1, y1) 到右下角 (x2, y2) 的区域和时,同样利用容斥原理:
结果 = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1]

