一维前缀和

一维前缀和主要是来解决快速计算一维区间和的问题

思考步骤

在需要计算大量的区间和时，如果暴力循环a数组去做每次都要花费O(n)的时间。 但是如果我们去构建一个数组s，每个元素是原数组当前位置之前元素的和。 那么在每次计算原数组的区间和a[n],a[n+1],...,a[m]时，只需计算s[m]-s[n-1]，每次的计算时间为O(1),相当于用空间来换时间。

公式

• 构建公式 s[i]=s[i-1]+a[i]
• 计算公式 s[m]-s[n-1]

实现

具体题目和讲解

#include <bits/stdc++.h>

using namespace std;

const int N=1e6+10;

int n,m;
int q[N],s[N];


int main()
{
    
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>q[i];
    for(int i=1;i<=n;i++) s[i]=s[i-1]+q[i];
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        cout<<s[b]-s[a-1]<<endl;
    }
    return 0;
}

二维前缀和

二维前缀和和一维类似，只不过变成求矩阵的和

公式

• 构建公式 s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]
• 使用公式 s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]

实现

具体题目和讲解

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3+10;
int n, m,q;
int a[N][N], s[N][N];


int main()
{
	
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=m;j++) 
	    {
	        cin>>a[i][j];
                s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
	    }
	        
    while(q--)
    {
        int x1,x2,y1,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]<<endl;
        
    }
	return 0;
		
}