前缀和：快速求出数组中某连续区间的和

一.一维前缀和(模板)

1.题目：【模板】前缀和_牛客题霸_牛客网 (nowcoder.com)

给定一个长度为n的数组a1,a2,....ana1​,a2​,....an​.，接下来有q次查询, 每次查询有两个参数l, r，对于每个询问, 请输出al+al+1+....+aral​+al+1​+....+ar​

2.算法思想

<1>预处理出一个前缀和数组

dp[i]表示[1,i]区间内所有元素的和

dp[i]=dp[i-1]+nums[i]

<2>使用前缀和数组

[l,r]区间内的元素和为dp[r]-dp[l-1]

Q：为什么下标从1开始计数呢？

A：为了处理边界情况，防止越界返回

3.时间复杂度：O(q)+O(n)

4.代码实现

#include <iostream>
#include<vector>
using namespace std;int main() {int n,q;cin>>n>>q;//读入数据vector<int> nums(n+1);for(int i=1;i<=n;i++){cin>>nums[i];}//预处理一个前缀和数组vector<long long> dp(n+1);for(int i=1;i<=n;i++){dp[i]=dp[i-1]+nums[i];}//使用前缀和数组int l=0,r=0;while(q--){cin>>l>>r;cout<<dp[r]-dp[l-1]<<endl;}
}

二.二维前缀和(模板)

1.题目：【模板】二维前缀和_牛客题霸_牛客网 (nowcoder.com)

给你一个 n 行 m 列的矩阵 A ，下标从1开始。接下来有 q 次查询，每次查询输入 4 个参数 x1 , y1 , x2 , y2请输出以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和，

2.算法思想

<1>预处理一个前缀和矩阵

dp[i][j]表示：[1,l]和[i,j]所围成的矩阵中所有元素的和

dp[i][j]=dp[i-1][j]+dp[i][j-1]+nums[i][j]-dp[i-1][j-1]

<2>使用前缀和矩阵

矩阵内元素和为:dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]

3.时间复杂度：O(m*n)+O(q)

4.代码实现

#include <iostream>
#include<vector>
using namespace std;int main() {int n,m,q;cin>>n>>m>>q;//读入数据vector<vector<int>> nums(n+1,vector<int>(m+1));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>nums[i][j];}}//创建一个前缀和矩阵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]+nums[i][j]-dp[i-1][j-1];}}//使用前缀和矩阵int x1=0,y1=0;int x2=0,y2=0;while(q--){cin>>x1>>y1;cin>>x2>>y2;cout<<dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]<<endl;}}