前缀和算法

用户11719958

发布于 2025-12-30 14:53:10

940

一，一维前缀和模板

1，题目描述

给你一个数组arr，进行q次询问，每次询问数组区间[l,r]的和。

2，思路

解法一:模拟该过程，每进行一次询问，遍历一次数组。时间复杂度为O(n*q)，会超时。

解法二：使用前缀和数组，图示：

3，代码实现

#include <iostream>
using namespace std;
#include<vector>

int main() 
{
     int n,q;
     cin>>n>>q;
     vector<int> arr(n+1);
     for(int i=1;i<=n;i++)
     cin>>arr[i];

     //创建dp表
     vector<long long> dp(n+1);//防止溢出
     //初始化
     for(int i=1;i<=n;i++)
     dp[i]=dp[i-1]+arr[i];

     int l,r;
     //使用dp表
     while(q--)
     {
        cin>>l>>r;
        cout<<dp[r]-dp[l-1]<<endl;
     }
}

二，二维前缀和模板

1，题目描述

2，思路

解法一：暴力解法—>模拟该过程，遍历矩阵，时间复杂度O(n*m*q)

解法二：前缀和矩阵图示：

3,代码实现

#include <iostream>
using namespace std;
#include <vector>
int main() 
{
    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];

    //预处理前缀和矩阵
    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];

    //使用前缀和矩阵
    int x1,x2,y1,y2;
    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;

}