$\color{green}{<–画图不易,点下这里赞一下吧}$
视频题解【前缀和】: https://www.acwing.com/video/5395/
什么是前缀和?
-
数列的和时,Sn = a1+a2+a3+…an; Sn就是数列的前 n 项和。
-
前缀和就是新建一个数组,新建数组中保存原数组前 n 项的和。
前缀和有什么用?
-
快速求某个区间中所有元素的加和。
-
例 S4 = a1 + a2 + a3 + a4; S1 = a1。所以可以通过 S4-S1 得到 a2+a3+a4 的值。
代码:
#include <iostream>
using namespace std;
const int N = 100010;
int a[N];//保存原数组
int s[N];//保存前缀和
int main(){
int n, m;
cin >> n >> m;
//从a[1]开始保存。a[0]是0
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
s[0] = 0;
//计算前缀和
for(int i = 1; i <= n; ++i)
s[i] = s[i - 1] + a[i];
for(int i = 0; i < m; ++i){
int l, r;//保存区间
cin >> l >> r;
//s[r] = a[1]+ ··· + a[r]
//s[l - 1] = a[1]+ ··· + a[l - 1]
//s[r] - s[l - 1] = a[l] + ··· + a[r]
cout << s[r] - s[l - 1] << endl;
}
}
看看我的
为什么
S[L-1]
要-1图标为a[l] 要加在里面
图确实不错哦
大佬,可以告诉我怎么做这种图吗,我看你题解上面的图都挺好的
看背景和字体好像是starUML
有些是ppt,有些是press