前缀和

什么是前缀和？

前缀和是一个数组的某项下标之前(包括此项元素)的所有数组元素的和。

作用：快速求出某一段区间的总和

such as:求出a[3]+a[4]+…+a[15]=sum[15]-sum[2] //sum为前缀和

优势：可以在O(1)的复杂度求出某一部分的总和

设b[]为前缀和数组，a[]为原数组，根据这句话可以得到前缀和的定义式和递推式：

【一维前缀和】

根据上面的定义，我们可以很容易得到 sum[i] = sum[i-1] + a[i] 　　这样就可以得到前i个数的和

根据上述表达式我们可以以O(1)求出区间[i,j]的区间和

【二维前缀和】

推导公式：

总体而言，其实他们就等于：