前缀和算法 课堂复习笔记

一、基础概念与核心公式

1. 前缀和数组定义

s[i] 表示原数组 a 中前 i 项的总和，通过递推计算：

• 数组下标统一从 1 开始，默认 s[0] = 0（全局变量自动初始化为 0），避免区间左端点为 1 时越界。
• 预处理时间复杂度：O(n)

2. 区间和快速计算

区间：数组中一段连续的范围，用左端点 L、右端点 R 表示，记为 [L, R]。

区间 [L, R] 的元素和公式：

• 单次查询时间复杂度：O(1)，远优于暴力遍历。

基础代码模板

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10; // 根据题目数据范围调整
int n, a[N], s[N];

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i-1] + a[i]; // 前缀和递推
    }
    // 求 [L,R] 区间和：s[R] - s[L-1]
    return 0;
}

二、定长区间枚举（滑动窗口思想）

当需要枚举所有长度固定为 k 的连续区间时，用双指针同步移动，无需重复计算。

写法规则

• 左端点 l 从 1 开始，右端点 r = l + k - 1
• 每次循环 l++、r++，直到 r 超出数组长度 n

代码模板（以区间长度 4 为例）

int main() {
    int k = 4; // 区间长度
    for(int l = 1, r = k; r <= n; l++, r++) {
        // 当前处理区间 [l, r]
        // 区间和直接用：s[r] - s[l-1]
    }
    return 0;
}

三、前缀和通用扩展：统计类前缀和

前缀和的本质是累加可叠加的统计量，不仅可以求和，还能统计区间内满足某条件的元素个数。

核心思路

满足条件的元素记为 1，不满足记为 0，再对 0/1 数组做前缀和。

典型例题：统计区间内偶数个数

• 定义 s[i]：前 i 个数中偶数的数量
• 递推规则：a[i] 是偶数则 +1，否则不变
• 区间 [L,R] 偶数个数：s[R] - s[L-1]

完整代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, q, a[N], s[N];

int main() {
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        if(a[i] % 2 == 0) s[i] = s[i-1] + 1;
        else s[i] = s[i-1];
    }
    for(int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l-1] << endl;
    }
    return 0;
}

通用结论：所有「区间内满足条件的元素数量」类问题，都可以用 0/1 前缀和解决。

四、经典题型：数组分割最小差值

题意

将数组分成前后连续的两部分，找到两部分和的差值最小时的分割位置。

解题思路

1. 预处理前缀和数组，数组总和为 s[n]
2. 枚举分割点 i：前 i 个元素为第一组，剩余元素为第二组
   • 第一组和：s1 = s[i]
   • 第二组和：s2 = s[n] - s[i]
   • 差值：abs(s1 - s2)
3. 遍历所有分割点，记录差值最小的位置

完整代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n, a[N], s[N];

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i-1] + a[i];
    }
    
    int min_diff = 1e9; // 记录最小差值，初始设为极大值
    int split_pos = 0;  // 记录最优分割点
    // 分割点范围 1 ~ n-1：保证两部分都至少有1个元素
    for(int i = 1; i <= n-1; i++) {
        int s1 = s[i];
        int s2 = s[n] - s[i];
        int diff = abs(s1 - s2);
        if(diff < min_diff) {
            min_diff = diff;
            split_pos = i;
        }
    }
    // 输出分界的两个位置
    cout << split_pos << " " << split_pos + 1;
    return 0;
}

五、高频易错点总结

1. 下标必须从 1 开始 保证 L=1 时 L-1=0 对应 s[0]=0，不会出现数组越界错误。

2. 数组大小预留充足 根据题目数据范围开数组，通常多开 10~20 个位置，避免边界越界。

3. 初始值规范

   • 前缀和数组 s[0] = 0，全局变量自动初始化为 0，无需手动赋值
   • 求最小值时初始值设为极大值（如 1e9），求最大值设为极小值（如 -1e9）

4. 分割点边界 数组分割问题中，分割点范围是 1 ~ n-1，不能取到 n（否则第二部分为空，无意义）。