前缀和:修订间差异

来自吾萌百科
无编辑摘要
无编辑摘要
第10行: 第10行:


一个部分和即数列A某个下标区间内的数的和,可表示为前缀和相减的形式:<math>sum(l,r)=\sum_{j=l}^r{A_j}=S_r-S_{l-1}</math>
一个部分和即数列A某个下标区间内的数的和,可表示为前缀和相减的形式:<math>sum(l,r)=\sum_{j=l}^r{A_j}=S_r-S_{l-1}</math>
== 例子 ==
<syntaxhighlight lang="c" line>
#define SIZE 100001
int S[SIZE];
void init(int* A, int n) {
S[0] = A[0];
for (int i = 1; i < n; ++i)
S[i] = S[i - 1] + A[i];
}
int add(int l, int r) {
return S[r] - S[l - 1];
}
<syntaxhighlight>


== 参考资料 ==
== 参考资料 ==
# 算法竞赛进阶指南,李煜东,21~22页
# 算法竞赛进阶指南,李煜东,21~22页
[[Category:计算机]]
[[Category:计算机]]

2022年2月19日 (六) 16:39的版本

对于一个给定的数列A,它的前缀和数列S的定义是:[math]\displaystyle{ S_i=\sum_{j=1}^i{A_j} }[/math]

你可以很简单的用递推来计算出一个数列的前缀和: [math]\displaystyle{ S_i=\begin{cases} A_1 &i=1 \\ S_{i-1}+A_i&i\gt 1 \end{cases} }[/math]

一个部分和即数列A某个下标区间内的数的和,可表示为前缀和相减的形式:[math]\displaystyle{ sum(l,r)=\sum_{j=l}^r{A_j}=S_r-S_{l-1} }[/math]

例子

<syntaxhighlight lang="c" line>

  1. define SIZE 100001

int S[SIZE];

void init(int* A, int n) { S[0] = A[0]; for (int i = 1; i < n; ++i) S[i] = S[i - 1] + A[i]; }

int add(int l, int r) { return S[r] - S[l - 1]; } <syntaxhighlight>


参考资料

  1. 算法竞赛进阶指南,李煜东,21~22页