本文主要是介绍前缀和与差分（一），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

前缀和与差分

前缀和

前缀和是指某序列的前n项和，可以把它理解为数学上的数列的前n项和，而差分可以看成前缀和的逆运算。合理的使用前缀和与差分，可以将某些复杂的问题简单化。

问题引入

输入一个长度为n的整数序列。接下来再输入m个询问，每个询问输入一对l, r。对于每个询问，输出原序列中从第l个数到第r个数的和。

用暴力的方式 很容易实现，时间复杂度是O（n*m）。

但是如果我们进行预处理

const int N=1e7+5;
int sum[N],a[N];

for (int i=1;i<=n;i++)
{
	sum[i]=sum[i-1]+a[i];//即   sum[i]表示a[1]~a[i]的和
}

根据高中的数列知识很容易知道 a[i]=sum[i]-sum[i-1];

cout<<sum[i]-sum[i-1];//查询i开始到i结束的值
l~r 即可表示为：
（sum[r]-sum[r-1]）+(sum[r-1]-sum[r-1-1])+...+sum[l]-sum[l-1];
化简成
sum[r]-sum[l-1];

 输出原序列中从第l个数到第r个数的和。

cout<<sum[r]-sum[l-1];

即可解决，这样每次查询只用 输出结果即可，查询复杂度为O（1），这也是一维前缀和。

例题1

P1115 最大子段和

思路：

首先我们会考虑和之前一样的进行预处理 然后用两个for 遍历所有的查询，每次保留最大的。时间复杂度O（n*n）

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int sum[N], a[N];
int n;
int ans = -0x3f;
int main ()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		sum[i] = sum[i - 1] + a[i];
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = i; j <= n; j++) //考虑到是求最长字段和   我认为 一个也算字段
		{
			ans = max(ans, sum[j] - sum[i - 1]);	//想到特判   i==0的时候，sum[1]-sum[0],全局变量sum[0]==0
		}
	}
	cout << ans;
}

提交

TLE

这篇关于前缀和与差分（一）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！