Prefix Sum
•Add the prefixes of a sequence of n numbers, x1, x2, …, xn.  That is, yk = Si£k  xi
•
•x1 = 3   x2 = 1   x3 = 4   x4 = 1   x5 = 5  x6 = 9
•y1 = 3 = 3
•y2 = 3+1 = 4
•y3 = 3+1+4 = 8
•y4 = 3+1+4+1 = 9
•y5 = 3+1+4+1+5 = 14
•y6 = 3+1+4+1+5+9 = 23