大纲

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 <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <list>
#include <limits.h>
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;
}