JZTXT

前缀和

发布时间 2023-07-23 09:52:20作者: So_noGeirf

在学完数组后常会遇见这样的题如B3612【深进1.例1】求区间和：

有n个数,$ a1,a2,a3.....an(ai<=105),m<=103$ ,$l$,$r$，求区间内的和;

$n$个数：$2$ $7$ $9$ $1$ $3$ $6$ $5$ $3$

你会写出这样的代码：

while(m--){
	for(int i=起点;i<=终点;i++)
		sum+=a[i];
	...............

抛开题目，我们来说一下前缀和优化

有$8$个数：$a[1]$~$a[9]$:

$a$ :$1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$

创建一个$sum$数组,使得$sum[i]=$从第$1$项到第$i$项之和

$ sum[i]=a[1]+a[2]...+a[i] $

$ a[1]+a[2]..+a[i-1]=sum[i-1] $

  • 得到一个前缀和公式：$ sum[i]=sum[i-1]+a[i] $

得到Code：

#include<iostream>
using namespace std;
int a[9]={0,1,2,3,4,5,6,7,8};
int sum[9];
int main(){
	sum[1]=a[1];
	for(int i=2;i<=8;i++)
		sum[i]=sum[i-1]+a[i];
	for(int i=1;i<=8;i++)
		cout<<sum[i]<<" ";
	return 0;
}

标准前缀和：

#include<iostream>
using namespace std;
long long a[100005],n;
long long sum[100005];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=a[i]+sum[i-1];
	}
	for(int i=1;i<=n;i++) cout<<sum[i]<<" ";
	return 0;
}

回到题目

通过前缀和公式，最早的题目B3612【深进1.例1】求区间和代码如下：

#include<iostream>
using namespace std;
long long a[100005],n,m;
long long sum[100005];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=a[i]+sum[i-1];
	}
	for(int i=1;i<=m;i++){
		int l,r;
		cin>>l>>r;
		cout<<sum[r]-sum[l-1];
	}
	return 0;
}

例题：P5745 【深基附B例】区间最大和

方法：前缀和 $+$ 二分

Code:

#include<iostream>
#include<cmath>
using namespace std;
long long a[4000005],n,m;
long long sum[4000005],maxn,mi,mj;
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=a[i]+sum[i-1];
	}
	for(int i=1;i<=n;i++){
		int l=i,r=n,mid;
		while(l<=r){
        	mid=(r+l)/2;
        	if(sum[mid]-sum[i-1]>m) r=mid-1;
      		else l=mid+1;
    	}
    	if(sum[r]-sum[i-1]<=m){
    		if(sum[r]-sum[i-1]>maxn){
    			mi=i;
      			mj=r;
      			maxn=sum[r]-sum[i-1];
			}
		}
	}
	cout<<mi<<" "<<mj<<" "<<maxn;
	return 0;
}