前缀和

前言

前缀和是应用于顺序表的算法，用来储存顺序表前n项的和。

所谓 部分和，就是给定一个数组，求它的某一段连续子数组的和。

比较传统的做法，就是对于要求部分和的区间 [l, r]，枚举所有的数进行相加，如下：

int partialSum(int *a, int l, int r) {
    int i;
    int s = 0;
    for(i = l; i <= r; ++i) {
        s += a[i];
    }
    return s;
}

此时时间复杂度最坏为O(mn)。有没有办法优化呢？

我们可以用一个 sum[] 数组来表示数组的前缀和，即 sum[i] 表示的是前 i 项的和，数学公式如下：

$sum[i] = \sum_{k=0}^{i}a[k]$

将 i-1 代入上述的 i，得到

$sum[i-1] = \sum_{k=0}^{i-1}a[k]$

于是可以得到

$sum[i]=sum[i-1]+a[i]$

注意由于sum[-1]非法，因此应当单独定义sum[0] = a[0]。

然后，我们继续来看部分和，有了前缀和数组 sum[] 以后，我们就可以利用差分法，在 O(1) 的时间内求得部分和，原因就是：

$\sum_{k=l}^{r}a[k]=\sum_{k=0}^{r}a[k]-\sum_{k=0}^{l-1}a[k]=sum[r]-sum[l-1]$

于是，只要预先将前缀和全部求出来，后面每次询问都可以做到 O(1) 了。

顾名思义，我们可以用一个 prod[] 数组来表示数组的前缀积，即 prod[i] 表示的是前 i 项的积，数学公式如下：

$prod[i]=\prod_{k=0}^{i}a[k]$

将 i-1 代入上述的 i，得到：

$prod[i-1]=\prod_{k=0}^{i-1}a[k]$

于是可以得到

$prod[i]=prod[i-1]\times a[i]$

同样，还有前缀异或和，同样满足这个性质，如下：

$xsum[i]=xsum[i-1] \ xor \ a[i]$

其中xor为异或运算符^。（因为不知道在LaTex语法里要怎么打出这个符号所以就这样代替了……）