算法中有前缀和这样一种很好的数据结构，它能极大地降低区间查询的时间复杂度
前缀和 - Prefix Sum
它是这样的，假如有这样一个数组(序列), A = [a1, a2, a3, a4, a5, a6, a7, a8] ==> 那么它的前缀和 Prefix Sum数组应该是如下： prefixSum = [sum1, sum2, sum3, sum4, sum5, sum6, sum7, sum8]
它的计算方式是这样的： sum1 = a1;
sum 2 = a1 + a2 = sum1 + a2
sum3 = a1 + a2 + a3 = sum2 + a3
sum4 = a1 + a2 + a3 + a4 = sum3 + a4
sum5 = a1 + a2 + a3 + a4 + a5 = sum4 + a5
标签：前缀,Sum,a3,a1,Prefix,a2,a4 From： https://www.cnblogs.com/wphl-27/p/17134695.html