一维与二维前缀和的常用写法
前缀和是很典型的'先算一遍，后面查得快'的做法。题目一旦变成'多次区间求和'，它基本就是第一批能想到的优化手段。思路不复杂，关键是把下标和公式写对，不然很容易在 l-1、x1-1 这些地方出错。
一、一维前缀和
题目描述
给定一个长度为 n 的数组，以及 m 次询问。每次询问给出两个整数 l 和 r，要求计算区间 [l, r] 中所有数的和。
算法思路
直接枚举每次区间里的元素，时间复杂度是 O(m * n)，数据大一点就不够用了。更省事的办法是先把前缀和数组算出来，之后每次查询都能在 O(1) 内完成。
设 dp[i] 表示区间 [1, i] 中所有数的和，那么状态转移就是：
dp[i] = dp[i - 1] + arr[i]
区间 [l, r] 的和可以直接写成：
s = dp[r] - dp[l - 1]
这里最容易忘的是 dp[0] 需要默认是 0。一般把数组下标从 1 开始写，会更顺手。
代码实现
#include <cmath>
#include <iostream>
using namespace std;
const int N = 100001;
long long dp[N];
int arr[N];
int n, m;
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> arr[i];
dp[i] = dp[i - 1] + arr[i];
}
while(m--){
int l, r;
cin >> l >> r;
cout << dp[r] - dp[l - 1] << endl;
}
return 0;
}
二、二维前缀和
题目描述
给定一个 的二维数组，以及 次查询。每次查询给出 ，要求计算以 为左上角、 为右下角的子矩阵中所有数的和。
