无编辑摘要 |
无编辑摘要 |
||
| 第3行： | 第3行： | ||
你可以很简单的用递推来计算出一个数列的前缀和： | 你可以很简单的用递推来计算出一个数列的前缀和： | ||
<math> | <math> | ||
S_i | S_i=\begin{cases} | ||
A_1 &i=1 \\ | A_1 &i=1 \\ | ||
S_{i-1}+A_i | S_{i-1}+A_i&i>1 | ||
\end{cases} | \end{cases} | ||
</math> | </math> | ||
2022年2月19日 (六) 15:59的版本
对于一个给定的数列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]
参考资料
- 算法竞赛进阶指南，李煜东，21~22页