前缀和--一维和二维模板

前缀和

【模板】前缀和

描述

给定一个长度为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;
}

原文地址：https://blog.csdn.net/Mr_Xuhhh/article/details/143025272

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！