前缀和算法

概念

今天简单学习了一下前缀和算法，什么是前缀和呢？

前缀和分为一维前缀和和二维前缀和等！对于一个长度为n的数组，前缀和就是前i个元素的和(i从1到n)
例如：
s[i]= \(\sum_{j=1}^{i}\)A[j]
性质：sum[l,r]=s[r]-s[l-1]

n=5  //假如a数组长度为5,存放1 2 3 4 5  s[5]存放前i个元素的前缀和
1 2 3 4 5
s[1]=a[1]=1
s[2]=a[1]+a[2]=3
s[3]=a[1]+a[2]+a[3]=6
s[4]=a[1]+a[2]+a[3]+a[4]=10
s[5]=a[1]+a[2]+a[3]+a[4]+a[5]=15

一维前缀和问题

//一维前缀和
#include<iostream>
#include<vector>
using namespace std;
int main()
{
	int n;
	cin >> n;
	vector<int>a(n, 0);
	vector<int>s(n + 1, 0);//为啥n+1，因为s[0]=0
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	for (int i = 0; i < n; i++)
	{
		s[i + 1] = s[i] + a[i];
	}
	int l, r;//闭区间[l,r] 若有m次询问，则用一个for循环
	cin >> l >> r;
	cout << s[r] - s[l - 1] << endl;;
}

核心函数：

//输入a[0~n-1] s[0~n]
s[0]=0
for(int i=0;i<n;i++)
s[i+1]=s[i]+a[i];

应用：leetcode 560 和为K的子数组

该题可以运用一维前缀和来做，简单的不优化的话，时间复杂度为O(n²),空间复杂度为O(n),暴力直接超时！
java代码：

class Solution {
    public int subarraySum(int[] nums, int k) {
    int sum=0;
    int n=nums.length; 
    int[] a=new int[n+1];
    a[0]=0;
    for(int i=0;i<n;i++)
      a[i+1]=a[i]+nums[i];
    for(int i=0;i<n;i++)//遍历子数组
    for(int j=i+1;j<=n;j++)
    {
        if((a[j]-a[i])==k)
        sum++;
    }
    return sum;
    }
}

beats：15% 还能够进行优化，后续更新！

二维前缀和问题

s[i][j]= \(\sum_{p=1}^{i}\)\(\sum_{q=1}^{j}\)A[i][j]
对于二维前缀和问题，我们需要求出它的二维前缀和数组：具体如何实现看图：
求红色部分前缀和：

可以看成：蓝色部分+粉色部分-黄色部分+自己a[i][j]相当于一个方块
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]
性质：sum[l1,r1,l2,r2]=s[l2,r2]-s[l2,r1]-s[l1,r2]+s[l1][r1]
//l1,rl为区间前a[l1][r1]的前缀和
//l2,r2为区间前a[l2][r2]的前缀和

c++代码

#include<iostream>
using namespace std;
const int maxn = 1000;
int s[maxn][maxn];
int a[maxn][maxn];
int main()
{
	int n, m;
	cin >> n >> m;
	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];
		}
	int l1, r1, l2, r2;
	cin >> l1 >> r1 >> l2 >> r2;
	int sum = s[l2][r2] - s[l2][r1] - s[l1][r2] + s[l1][r1]; //m次询问写一个循环
	cout << sum << endl;
}

前缀和算法

原文：https://www.cnblogs.com/SCPC-QACY/p/14728761.html