【c++入门（2）】前缀和

大纲

1.计算前缀和
2.计算字段和
3.后缀和
4.前缀积
5.后缀积
6.例题

1.计算前缀和
基础问题：
思路1：
枚举

cin ();
for (int i = 1; i <= q; i++)
{
	cin >> x;
	int sum = 0;
	for (int j = 1; j <= x; j++)
	{
		sum += a[j];
	}
	cout << sum << endl;
}

时间复杂度：O(QN) 极端情况时间复杂度会超！
思路2：
前缀和

可以发现：

以x的角度再来看看我们的发现有什么作用：

所以我们就可以用递推 + 查表 来做这道题：

sum[0] = 0;
	for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + A[i];
	for (int i = 1; i <= q; i++)
	{
		cin >> x;
		cout << sum[x] << endl;
	}

2.计算字段和
基础问题：

思路1：
枚举

cin ();
	for (int i = 1; i <= q; i++)
	{
		cin >> l >> r;
		int sum = 0;
		for (int j = l; j <= r; j++)
		{
			sum += a[j];
		}
		cout << sum << endl;
	}

同样以x的视角来看：
最后可以得出式子：
sum [ l, r ] = sum [ r ] - sum [ l - 1 ]
这样可以通过前缀和的思路来写这道题：

sum[0] = 0;
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + A[i];
for (int i = 1; i <= q; i++)
{
	cin >> l >> r;
	cout << sum[r] - sum[l - 1] << endl;
}

时间复杂度：O(n)
3.计算后缀和
其实后缀和就只是把前缀和反过来：
时间复杂度：O(n)。

4.前缀积
其实你只要懂了前缀和，你就很容易懂其他的，前缀积其实就是将计算前缀和的’+‘，换成’ * ’

时间复杂度：O(n)
5.后缀积
同样也是将前缀积反过来：

时间复杂度：O(n)
6.例题

互质序列
题目描述

你知道什么是“互质序列”吗？就是一个由n个正整数组成的序列，它们的GCD（最大公约数）等于1.这样的互质序列很容易找到。



但是我们可以尝试通过删除一个整数来最大化这些整数的GCD。

现在给出一个序列，请最大化其元素的GCD。


输入格式

第一行，一个整数T，表示测试数据的组数。

1≤T≤10

对于每组测试数据，第一行，一个整数n，表示序列中正整数的数量，3≤n≤100000

接下来一行，包含n个正整数a1,a2...an,表示序列中的元素，1≤ai≤10^9
输出格式

对于每组数据输出一行，一个整数，表示GCD的最大值
输入输出样列
输入样例1：

3
3
1 1 1
5
2 2 2 3 2
4
1 2 4 8

输出样例1：

1
2
2

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int n,a[100010],l[100010],r[100010];
int t;
int gcd(int x,int y){
	return y==0?x:gcd(y,x%y);
}
int main(){
	cin>>t;
	while(t--){
		cin>>n;
		int ans=0;
		memset(l,0,sizeof(l));
		memset(r,0,sizeof(r));
		for(int i=1;i<=n;i++){
			cin>>a[i];
			l[i]=gcd(l[i-1],a[i]);
		}
		for(int i=n;i>=1;i--) r[i]=gcd(r[i+1],a[i]);
		for(int i=1;i<=n;i++){
			ans=max(ans,gcd(l[i-1],r[i+1]));
		}
		cout<<ans<<endl;
	}
	return 0;
}