c语言实现一个前缀和的题

Question

如何用c语言实现一个前缀和呢？
不适合明白前缀的含义

Answer 1

1、部分和

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

2、朴素做法

  比较传统的做法，就是对于要求部分和的区间 $[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;
}

  函数的返回值代表了求 a[]数组的第 $l$ 项 到 第 $r$ 项的和，如果数组长度为 $n$，这样做的最坏时间复杂度为 $O(n)$。那么，试想一下，如果有 $m$ 次询问，每次询问都是$O(n)$，时间复杂度就会变成 $O(nm)$，有没有办法优化呢？

3、前缀和

  我们可以用一个sum[]数组来表示数组的前缀和，即sum[i]表示的是前 $i$ 项的和，数学公式如下：$$sum[i] = a[0] + a[1] + ... a[i] = \sum_{k=0}^{i} a[k]$$  将 $i-1$ 代入上述的 $i$，得到：$$sum[i-1] = a[0] + a[1] + ... a[i-1] = \sum_{k=0}^{i-1} a[k]$$ 于是可以得到 $$sum[i] = sum[i-1] + a[i]$$。

4、前缀和的边界值

  有了递推式，我们还需要有一个边界值，从定义出发，边界值应该是：$$sum[-1] = 0$$ 怎么理解呢？试想一下，$sum[1]$ 表示的是从 第0项 累加到 第1项； $sum[0]$ 表示的是从 第0项 累加到 第0项；$sum[-1]$ 表示的是一项都没有累加，那么这个值固然就是零了。即：$$sum[i] = \begin{cases} 0 & i = -1 \ sum[i-1] + a[i] & i \ge 0\end{cases}$$

5、边界处理

  这时候，我们需要注意 C 语言中的 下标是从零开始的，所以，$sum[-1]$会导致数组下标越界，可以将它转换成函数的形式将数组sum[]进行一次封装：

int prefixSum(int n) {
    if(n == -1) {
        return 0;
    }
    return sum[n];
}

6、再看部分和

  然后，我们继续来看部分和，有了前缀和数组sum[]以后，我们就可以利用差分法，在 $O(1)$ 的时间内求得部分和，原因就是：$$\begin{aligned} \sum_{k=l}^{r}a[k] &= a[l] + a[l+1] + ... a[r-1] + a[r] \ &= (a[0]+...+a[r]) - (a[0]+...+a[l-1] \ &= \sum_{k=0}^{r}a[k] - \sum_{k=0}^{l-1}a[k] \ &= sum[r] - sum[l-1] \end{aligned}$$
  于是，只要预先将前缀和全部求出来，后面每次询问都可以做到 $O(1)$。