【算法】前缀和——前缀和

本题主要用一个模板题目来说明前缀和的基本思想，有需要借鉴即可。

1.题目

题目链接：LINK

这个题目可以用暴力求解的思路来做的，只不过时间复杂度是O(N*Q)…

我们这里不谈暴力求解的思路，来介绍一种新的方法——前缀和。

我感觉前缀和方法本质上是一种用空间换时间的思路。

2.前缀和

2.1题目分析

暴力求解：题目要求我们求[l,r]区间的数字之和，我们暴力求解无非就是累加，sum = arr[l] + arr[l + 1] + … + arr[r]，显然有q次求值，时间复杂度就成了O(N*Q)，然后就时间复杂度太高了

暴力时间复杂度高的原因：但是暴力求解时间复杂度高的原因我们仔细想一想就不难发现，说白了就做了大量之前得出的和之后却一次一次又重新进行计算。

想法：所以我们根据以空间换时间的思想，只要把可能用到的和存一下，方便下一次用就行了。

2.2前缀和算法

第一步，先预处理一个前缀数组

比如说，题目给我们如下数组：

那我们可以搞一个前缀和数组，这个前缀和数组的i下标对应的值是arr数组[1,i]区间值的和。

这样直接遍历一遍arr就可以得到这个前缀和数组了：

第二步，由题计算得结果

题目要求我们给的是[l,r]这个区间的和，但是我们有的是[1,l-1],[1,l],[1,r]区间的和，其实我们给他做个差就能得到结果了，即：sum[l,r] = sum[1,r] - sum[1,l-1];

这个地方因为用到了l-1下标，为了防止出现0 - 1 = -1(-1下标对数组不存在)的情况，所以我们整体存值的时候把数组每个元素往前移动一个就行，把0位置空出来，0位置处置为0即可。当然，这个地方也可以做特殊判断来进行处理。

3.代码示例

#include <iostream>
using namespace std;
int main() 
{
    //读取数据
    size_t n = 0, q = 0;
    cin >> n >> q;
    long arr[n + 1];
    arr[0] = 0;
    for(size_t i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }
    //创建前缀和数组
    long summary[n + 1];   
    //求前缀和
    summary[0] = 0;
    for(size_t i = 1; i <= n; i++)
    {
        summary[i] = summary[i - 1] + arr[i];
    }
    //输出结果
    while(q--)
    {
        int l, r;
        cin >> l >> r;
        cout << (summary[r] - summary[l - 1]) << endl;
    }
    
    return 0;
}

4.总结

前缀和算法本质是一种“以空间换时间”的思想，其实这个很简单，我没听老师讲这个算法的时候好像就用过这个思想做过一道差不多的题目。这个思想很简单，但是题目不好说，上面的题目仅仅是个模板题而已…

我觉得我们在处理一些题目时候就可以借鉴“以空间换时间”的这一思想，省去大量重复计算，从而提高效率。

EOF