前缀和

来自吾萌百科
Rmolives讨论 | 贡献2022年2月19日 (六) 15:53的版本

对于一个给定的数组A,它的前缀和数列S是能通过递推能求出的基本信息之一:[math]\displaystyle{ S_i=\sum_{j=1}^i{A_j} }[/math]

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

参考资料

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