前缀和--一维和二维模板
前缀和
【模板】前缀和
描述
给定一个长度为n的数组a1,a2,…ana1,a2,…a**n.
接下来有q次查询, 每次查询有两个参数l, r.
对于每个询问, 请输出al+al+1+…+ara**l+a**l+1+…+a**r
输入描述：
第一行包含两个整数n和q.
第二行包含n个整数, 表示a1,a2,…ana1,a2,…a**n.
接下来q行,每行包含两个整数 l和r.
1≤n,q≤1051≤n,q≤105
−109≤a[i]≤109−109≤a[i]≤109
1≤l≤r≤n1≤l≤r≤n
输出描述：
输出q行,每行代表一次查询的结果.
示例1
输入：
3 2
1 2 4
1 2
2 3
输出：
3
6
题目解析：
解法（前缀和）：
算法思路：
a. 先预处理出来⼀个「前缀和」数组：
⽤ dp[i] 表⽰： [1, i] 区间内所有元素的和，那么 dp[i - 1] ⾥⾯存的就是 [1, i - 1] 区间内所有元素的和，那么：可得递推公式： dp[i] = dp[i - 1] + arr[i] ；
b. 使⽤前缀和数组，「快速」求出「某⼀个区间内」所有元素的和：
当询问的区间是 [l, r] 时：区间内所有元素的和为： dp[r] - dp[l - 1] 。
代码如下：
#include <iostream>
#include <vector>
using namespace std;
int main() {
//1.读入数据
int n,q;
cin>>n>>q;
vector<int> arr(n+1);
for(int i=1;i<=n;i++) cin>>arr[i];
//2.预处理来一个前缀和数组
vector<long long> dp(n+1);//用long long是为了防止溢出
for(int i=1;i<=n;i++) dp[i]=dp[i-1]+arr[i];
//3.使用前缀和数组
int l=0,r=0;
while(q--)
{
cin>>l>>r;
cout<<dp[r]-dp[l-1]<<endl;
}
return 0;
}
【模板】二维前缀和
描述
给你一个 n 行 m 列的矩阵 A ，下标从1开始。
接下来有 q 次查询，每次查询输入 4 个参数 x1 , y1 , x2 , y2
请输出以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和，
输入描述：
第一行包含三个整数n,m,q.
接下来n行，每行m个整数，代表矩阵的元素
接下来q行，每行4个整数x1, y1, x2, y2，分别代表这次查询的参数
1≤n,m≤10001≤n,m≤1000
1≤q≤1051≤q≤105
−109≤a[i][j]≤109−109≤a[i][j]≤109
1≤x1≤x2≤n1≤x1≤x2≤n
1≤y1≤y2≤m1≤y1≤y2≤m
输出描述：
输出q行，每行表示查询结果。
示例1
输入：
3 4 3
1 2 3 4
3 2 1 0
1 5 7 8
1 1 2 2
1 1 3 3
1 2 3 4
输出：
8
25
32
代码如下：
#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]<<endl;
}
return 0;
}