一维前缀和
一维前缀和是一种高效处理数组区间求和问题的算法，通过预处理数组构建前缀和数组，能将区间和查询的时间复杂度从 O(n) 降至 O(1)。
这种算法专门用来处理多次求区间和的问题。
1.1 一维前缀和原理讲解
预处理方式如下：前缀和数组的第 0 个位置通常置为 0。这样在代码实现时，当前位置的值等于前一个位置的值加上原数据当前位置的值，无需特判第一个位置。
若要求某一段区间的和，则用结尾位置的值减去区间开头位置减 1 的值。这是因为区间开头的位置也是需要的，减 1 后的位置才是需要去掉的部分。
1.2 具体代码实现以及例题讲解
以下代码演示了如何构造一维前缀和数组并计算区间和。当数据量 n 较大时，暴力解法会超时，而使用前缀和可将单次查询优化至 O(1)。
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<long long> nums(n + 1);
vector<long long> dp(n + 1);
for (int i = 1; i <= n; ++i) cin >> nums[i];
for (int i = 1; i <= n; ++i) dp[i] = dp[i - 1] + nums[i];
while (m--) {
int l, r;
cin >> l >> r;
long long sum = dp[r] - dp[l - 1];
cout << sum << endl;
}
return 0;
}
二、二维前缀和
二维前缀和是一维前缀和在二维矩阵场景下的扩展，专门用于高效计算矩阵中任意子矩形区域的元素总和。它通过预处理构建前缀和矩阵，将单次子区域和的查询时间优化到 O(1)，非常适合需要频繁查询二维区域和的场景。
