算法基础：一维前缀和与最大子段和实战

前缀和核心思想

前缀和与差分的本质是预处理。在暴力枚举查询时，通过空间换时间，将区间求和的时间复杂度从 O(n) 降至 O(1)。这是算法优化中非常经典的思路。

一维前缀和原理

构建数组

设原数组为 a，前缀和数组为 f。核心递推公式如下：

f[i] = f[i - 1] + a[i]

注意：通常采用 1-based 索引（即下标从 1 开始），这样 f[0] 默认为 0，计算 f[l-1] 时不会越界，逻辑也更清晰。

区间查询

求区间 [l, r] 的元素和，利用前缀和数组只需一次减法：

sum = f[r] - f[l - 1]

经典实战

1. 一维前缀和模板

直接应用上述公式即可。输入 n 个数字，m 次查询。这里需要注意数据类型，累加值可能超过 int 范围，建议使用 long long。

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
LL a[N];
LL f[N];

int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    // 构建前缀和，f[0] 初始化为 0
    for(int i = 1; i <= n; i++) f[i] = f[i - 1] + a[i];
    while(m--) {
        int l, r;
        cin >> l >> r;
        cout << f[r] - f[l - 1] << endl;
    }
    return 0;
}

2. 最大子段和

这道题需要结合前缀和的思想。如果我们固定子段的右端点 i，那么要使子段和最大，就需要找到左端点 j (1 <= j <= i)，使得 f[i] - f[j-1] 最大。