前缀和是处理区间查询问题的高效技巧，核心思想是通过预处理将 O(N) 的查询优化为 O(1)。掌握这一模式，能显著提升在数组或矩阵相关题目中的解题效率。
一维前缀和
核心逻辑：
我们预先计算一个数组 dp，其中 dp[i] 表示原数组从下标 0 到 i 所有元素的累加和。这样，任意区间 [l, r] 的和就可以通过 dp[r] - dp[l-1] 快速得到。
这里有个细节要注意：为了处理边界情况（比如 l=0），通常会在代码中将前缀和数组开大一位，或者让下标从 1 开始，这样 dp[l-1] 就不会越界。
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
// 使用 n+1 大小，下标从 1 开始，方便处理边界
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;
// 区间 [l, r] 的和 = dp[r] - dp[l-1]
cout << dp[r] - dp[l - 1] << endl;
}
return 0;
}
二维前缀和
核心逻辑：
二维前缀和一维类似，但涉及面积计算。我们需要构建一个 矩阵，表示从 到 矩形区域内所有元素的累加和。
