Buer blog | 详情

什么是前缀和？

前缀和是指从数组的起始位置到某一位置的所有元素的和。前缀和算法一种用于高效计算数组前缀和的算法。

前缀和算法的基本步骤：

创建一个与原始数组相同长度的前缀和数组。初始时，前缀和数组的第一个元素与原始数组的第一个元素相同。
从第二个元素开始，遍历原始数组，计算每个位置处的前缀和，即将前一个位置的前缀和与当前位置的元素相加
将计算得到的前缀和存储到前缀和数组的相应位置。
完成遍历后，前缀和数组中存储了原始数组每个位置的前缀和值。

下面示例，演示如何使用前缀和算法计算数组的前缀和：

原始数组: [1, 2, 3, 4, 5] 
前缀和数组: [1, 3, 6, 10, 15]
【解释说明】
原始数组的前缀和：[1, 1+2, 1+2+3, 1+2+3+4, 1+2+3+4+5] = [1, 3, 6, 10, 15]

算法案例

【模板】前缀和

样例输入复制

样例输出复制

3
6

参考代码

#include <bits/stdc++.h>
using namespace std;
 
const int N = 100010;
long long arr[N], dp[N];
int n, q;
 
int main()
{
    cin >> n >> q;
    // 读取数据
    for(int i = 1; i <= n; i++) cin >> arr[i];
    // 处理前缀和数组
    for(int i = 1; i <= n; i++) dp[i] = dp[i - 1] + arr[i];
    while(q--)
    {
        int l, r;
        cin >> l >> r;
        // 计算区间和
        cout << dp[r] - dp[l - 1] << endl;
    }
    return 0;
}

【性能分析】

时间复杂度：

初始化前缀和数组：需要遍历整个原始数组，时间复杂度为O(n)。
对每个查询计算区间和：只需要进行常数次操作，时间复杂度为O(1)。
总体时间复杂度为O(n + q)，其中n表示数组长度，q表示查询次数。

空间复杂度：

空间复杂度为O(n)，其中n表示数组长度。需要额外的前缀和数组来存储计算得到的前缀和。

【注意】

这里有一个细节问题：为什么下标不从0开始，而是从 1 开始？

其实很简单，在该代码中，数组索引从1开始的原因是为了方便计算前缀和；

在前缀和算法中，我们需要维护一个前缀和数组，其中每个元素表示原始数组从开头到当前位置的累加和；如果数组索引从0开始，那么在计算前缀和时，需要特殊处理索引为0的情况，这会增加代码的复杂性。通过将数组索引从1开始，可以使得计算前缀和的逻辑更加简单和直观。例如，在第i个位置上的前缀和可以通过dp[i] = dp[i-1] + arr[i]来计算，而无需额外处理索引为0的情况。