Problem5181--学习系列——一维前缀和

5181: 学习系列——一维前缀和

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

【知识点】
前缀和是一种重要的预处理,能大大降低查询的时间复杂度。可以简单理解为“数列的前 $n$ 项的和”。
对于一维数组 A,它的一维前缀和为数组 B,定义如下:数组 B 的第 $i$ 个数是数组 a  第 $1$ 项到第 $i$ 个数的和。即
$B_i = \sum_{i=1}^{i}=A_1+A_2+ \dots + A_i$
这样我们可以得到以下的递推公式:
$B_1=A_1$
$B_2=A_1+A_2=B_1+A_2$
$B_3=A_1+A_2+A_3=B_2+A_3$
$\dots$
$B_N=A_1+A_2+ \dots + A_{N-1} +A_N$=$B_{N-1}+A_N$
从上面的递推公式可以看出。如果我们在数组 A 前面增加一项 $A_0=0$,在数组 B 前面增加一项 $B_0=0$,我们可以将 $B_1=A_1$ 改写为 $B_1=A_0+A_1=B_0+A1$。于是递推公式可以改写为:
$B_i=B_{i-1}+A_{i},\ i \in [1,\ N]$。
这样我们可以通过一个循环轻松实现。

【要求】
有 $N$ 个的正整数放到数组 A 里,现在要求你求出并输出这样一个数组:
这个数组的第 $i$个数是数组 A 的第一个到数组 A 的第 $i$个数的和。

Input

第一行一个正整数:$N\ (1 \leq N \leq 100)$,$N$ 表示数组 A 的长度。
第二行 $N$ 个正整数 $A_i\ (1 \leq A_i \leq 10,000)$。

Output

$N$ 个正整数。数组 A 对应的前缀和数组 B。

Sample 1 Input

6
2 6 1 9 7 3

Sample 1 Output

2 8 9 18 25 28

Source/Category

基础算法 4.2.前缀和