什么是前缀和
前缀和（Prefix Sum）的定义为：对于一个给定的数列 A, 它的前缀和数列 S 是通过递推能求出来得 ![S[i] = \sum_{j = 1}^{i}A[j]](https://javaforall.net/wp-content/uploads/2020/11/2020110817443450.jpg)
部分和。
例如：
C++实现
//假设数组a和前缀和数组s都已经定义 int i; //初始条件 a[0] = 0; s[0] = 0; for (i=1; i<=n; i++) { cin >> a[i]; s[i] = s[i-1] + a[i]; }模板题
下面我们用一个模板题，将完整的一维数组前缀和做一个简单的展示。题目链接http://47.110.135.197/problem.php?id=5181。
#include
using namespace std; int main() { int n; cin >> n; int data; int ans[102] = {}; for (int i=1; i<=n; i++) { cin >> data; ans[i] = ans[i-1] + data; } for (int i=1; i<=n; i++) { cout << ans[i] << " "; } cout << endl; return 0; }
用途
前缀和是一种重要的预处理，能大大降低查询的时间复杂度。
前缀和是以求和的方式灵活地面对区间询问。
下面我们用一个模板题来说明。
例题：区间求和
给你一串长度为 n 的数列 a1, a2, a3, …, an，再给出 m 个询问，每次询问给出 L, R 两个数，要求给出区间 [L, R] 里的数的和。
详细可以参看http://47.110.135.197/problem.php?id=5139。
题目分析
题目非常简单，我们也可以得到一个最简单的解法，暴力操作。也就是对应每个询问，我们都从 L 开始到 R 结束对这个区间的数据进行求和。基本的代码如下：
#include
using namespace std; const int MAXN = 1e5+2; long long arr[MAXN] = {}; int main() { int n; cin >> n; int i, j; for (i=1; i<=n; i++) { cin >> arr[i]; } int m; int l, r; long long ans = 0; cin >> m; for (i=0; i
> l >> r; ans = 0; for (j=l; j<=r; j++) { ans += arr[j]; } cout << ans << endl; } return 0; }
代码分析
从上面的代码非常明确的分析出来，代码的时间复杂度为 。也就是说，在比赛中这样的解法能否 AC，那就要看数据的量了。当然我们都知道这样的解法，比赛中是肯定不可能 AC。因此唯一的可能就是降低时间复杂度。方法就是使用前缀和。
我们先看前缀和的数学。数列A中某个下标区间 [l, r] 内的数的和定义为：
从上面推导，我们可以清晰的看出，前缀和和区间和的关系。
代码改进
#include
using namespace std; const int MAXN = 1e5+2; long long arr[MAXN] = {}; long long sum[MAXN] = {}; int main() { int n; cin >> n; int i, j; for (i=1; i<=n; i++) { cin >> arr[i]; sum[i] = sum[i-1] + arr[i]; } int m; int l, r; cin >> m; for (i=0; i
> l >> r; cout << sum[r] - sum[l-1] << endl; } return 0; }
代码分析
从上面的代码非常明确的分析出来，代码的时间复杂度为 。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/229738.html原文链接：https://javaforall.net
