前缀和算法通过预处理构建数组，将区间求和时间复杂度从 O(n) 降至 O(1)。一维前缀和利用 dp[i]=dp[i-1]+arr[i] 递推，查询区间 [l,r] 和为 dp[r]-dp[l-1]。二维前缀和在矩阵左上角补零行零列，递推公式 sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + matrix[i-1][j-1]，查询矩形区域和时利用容斥原理计算。文章提供 C++ 代码示例，适用于频繁区间或子矩阵求和场景。
给定一个长度为 n 的数组，进行 m 次查询，每次查询区间 [l, r] 内所有元素的和。
#include <iostream>
#include <vector>
using namespace std;
int main() {
// 1. 输入数据
int n = 0, m = 0;
cin >> n >> m;
vector<int> arr(n + 1);
for (size_t i = 1; i <= n; i++) {
cin >> arr[i];
}
// 2. 预处理一个 dp 数组，防止溢出使用 long long
vector<long long> dp(n + 1);
for (size_t i = 1; i <= n; i++) {
dp[i] = dp[i - 1] + arr[i];
}
// 3. 使用前缀和数组
int l = 0, r = 0;
while (m--) {
cin >> l >> r;
cout << dp[r] - dp[l - 1] << '\n';
}
return 0;
}
给定一个 n 行 m 列的矩阵，进行 q 次查询，每次查询子矩阵区域内所有元素的累加和。
类比于一维数组的形式，如果我们能处理出来从 [0, 0] 位置到 [i, j] 位置这片区域内所有元素的累加和，就可以在 O(1) 的时间内，搞定矩阵内任意区域内所有元素的累加和。
第一步：搞出来前缀和矩阵 在矩阵的最上面和最左边添加上一行和一列 0，省去边界条件的处理。下标直接从 1 开始，能大胆使用 i-1，j-1 位置的值。 注意：dp 表与原数组 matrix 内的元素的映射关系：从 dp 表到 matrix 矩阵，横纵坐标减一；从 matrix 矩阵到 dp 表，横纵坐标加一。
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]
第二步：使用前缀和矩阵 题目的接口中提供的参数是原始矩阵的下标，为了避免下标映射错误，这里直接先把下标映射成 dp 表里面对应的下标：row1++, col1++, row2++, col2++。 对于左上角 (row1, col1)，右下角 (row2, col2) 围成的区域，利用容斥原理计算： 红 = 整个面积 - (绿 + 黄) - (蓝 + 黄) + 黄 从而可得红色区域内的元素总和为： sum[row2][col2] - sum[row2][col1 - 1] - sum[row1 - 1][col2] + sum[row1 - 1][col1 - 1]
#include <iostream>
#include <vector>
using namespace std;
int main() {
// 1. 输入数据
int n = 0, m = 0, q = 0;
cin >> n >> m >> q;
vector<vector<int>> arr(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> arr[i][j];
}
}
// 2. 预处理
vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];
}
}
// 3. 使用前缀和
int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
while (q--) {
cin >> x1 >> y1 >> x2 >> y2;
cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << '\n';
}
return 0;
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online