01_Prefix Sums 前缀和

Prefix Sums 前缀和

什么是前缀和？

前缀和（Prefix Sum）是一种重要的预处理技术，用于快速计算数组任意区间内的元素和。

对于数组 a[1], a[2], ..., a[n]，定义前缀和数组 p：

p[i] = a[1] + a[2] + ... + a[i]

其中 p[0] = 0。

为什么需要前缀和？

在没有前缀和的情况下，计算数组区间 [l, r] 的和需要 O(r-l+1) 的时间。但使用前缀和后，区间和可以在 O(1) 时间内得到：

sum(l, r) = p[r] − p[l − 1]

---

前缀和的基本实现

构建前缀和数组

// 构建前缀和数组
vector<long long> prefix(n + 1);
prefix[0] = 0;
for (int i = 1; i <= n; i++) {
    prefix[i] = prefix[i-1] + a[i];
}

O(1) 区间求和

// 计算区间 [l, r] 的和（1-indexed）
long long query(int l, int r) {
    return prefix[r] - prefix[l-1];
}

---

经典例题

例题1： Breed Counting 统计区间内各品种数量

题目来源: USACO - Breed Counting

题目描述: 给定 N 头牛的品种（1=Holsteins, 2=Guernseys, 3=Jerseys），有 Q 次查询，每次查询区间 [a, b] 内各品种的牛数量。

解题思路: 多维前缀和

• 维护三个前缀和数组，分别统计每种品种的前缀数量
• 对于每次查询，直接用前缀和相减得到区间内各品种数量

代码实现:

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("bcount.in", "r", stdin);
    freopen("bcount.out", "w", stdout);

    int n, q;
    cin >> n >> q;

    // 三个前缀和数组
    vector<int> pref1(n + 1), pref2(n + 1), pref3(n + 1);

    for (int i = 1; i <= n; i++) {
        // 先复制前一个位置的值
        pref1[i] = pref1[i - 1];
        pref2[i] = pref2[i - 1];
        pref3[i] = pref3[i - 1];

        int x;
        cin >> x;
        if (x == 1) pref1[i]++;      // 品种1：Holsteins
        else if (x == 2) pref2[i]++; // 品种2：Guernseys
        else if (x == 3) pref3[i]++; // 品种3：Jerseys
    }

    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        // 区间 [l, r] 的各品种数量 = 前缀差
        cout << pref1[r] - pref1[l - 1] << " ";
        cout << pref2[r] - pref2[l - 1] << " ";
        cout << pref3[r] - pref3[l - 1] << "\n";
    }

    return 0;
}

时间复杂度: - 预处理：O(n) - 单次查询：O(1) - 总时间：O(n + q)

例题2：子数组和为7的倍数（求最长长度）

题目来源: USACO - Div7

题目描述: 给定 n 个数，求和为 7 的倍数的子数组的最长长度。

核心原理: 同余定理

• 如果 prefix[i] % 7 == prefix[j] % 7，则子数组 [i+1, j] 的和为 7 的倍数
• 因此，我们只需要找到相同余数之间的最大距离

解题思路:

1. 记录每个余数首次出现的下标
2. 当同一余数再次出现时，计算当前下标与首次下标的差值
3. 更新最大长度

代码实现:

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("div7.in", "r", stdin);
    freopen("div7.out", "w", stdout);

    int n;
    cin >> n;

    // 记录每个余数首次出现的下标，-1表示未出现
    vector<int> first_idx(7, -1);
    first_idx[0] = 0;  // 前缀和为0时，下标为0

    int current_sum = 0;
    int max_length = 0;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        current_sum = (current_sum + x) % 7;

        if (first_idx[current_sum] == -1) {
            // 该余数首次出现，记录下标
            first_idx[current_sum] = i;
        } else {
            // 该余数之前出现过，计算子数组长度
            max_length = max(max_length, i - first_idx[current_sum]);
        }
    }

    cout << max_length << "\n";
    return 0;
}

时间复杂度: O(n)

---

例题3：子数组和为目标值（数组全为正数）

题目来源: CSES - Subarray Sum I

题目描述: 给定一个长度为 n 的数组（元素均为正整数）和目标值 x，求子数组和等于 x 的个数。

解题思路: 由于数组元素全为正数，可以使用滑动窗口（双指针）求解。

• 当窗口和小于 x 时，右指针右移扩大窗口
• 当窗口和等于 x 时，计数加一，然后左指针右移缩小窗口
• 当窗口和大于 x 时，左指针右移缩小窗口

代码实现:

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    for (int& num : a) cin >> num;

    int l = 0, r = 0;
    int sum = a[0];
    int ans = 0;

    while (r < n) {
        if (sum < x) {
            // 窗口和小于目标，右移扩展
            r++;
            if (r < n) sum += a[r];
        } else if (sum == x) {
            // 找到一个满足条件的子数组
            ans++;
            sum -= a[l];
            l++;
        } else {
            // 窗口和大于目标，左移收缩
            sum -= a[l];
            l++;
        }
    }

    cout << ans << "\n";
    return 0;
}

时间复杂度: O(n)

---

例题4：子数组和为目标值（数组含负数）

题目来源: CSES - Subarray Sum II

题目描述: 给定一个长度为 n 的数组（可能含负数）和目标值 x，求子数组和等于 x 的个数。

解题思路: 使用哈希表记录前缀和出现的次数。

• 对于当前位置 i，前缀和为 prefix
• 如果之前存在前缀和为 prefix - x 的位置，则以当前位置结尾的子数组和为 x
• 利用组合数学：满足条件的子数组个数等于此前 prefix - x 出现的次数

代码实现:

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, target;
    cin >> n >> target;

    map<long long, long long> sums;
    sums[0] = 1;  // 空前缀，初始为1

    long long prefix_sum = 0;
    long long ans = 0;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        prefix_sum += x;

        // 累加 prefix_sum - target 出现的次数
        ans += sums[prefix_sum - target];

        // 记录当前前缀和
        sums[prefix_sum]++;
    }

    cout << ans << "\n";
    return 0;
}

时间复杂度: O(n log n) 或 O(n) 使用 unordered_map

---

例题5：子数组和为n的倍数（求个数）

题目来源: CSES - Subarray Divisibility

题目描述: 给定 n 个数，求和能够被 n 整除的子数组个数。

核心原理: 同余组合

• 如果 prefix[i] % n == prefix[j] % n，则子数组 [i+1, j] 的和能被 n 整除
• 统计每个余数出现的次数 cnt，该余数贡献的子数组个数为 C(cnt, 2) = cnt * (cnt - 1) / 2

代码实现:

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<long long> cnt(n, 0);
    cnt[0] = 1;  // 前缀和为0时，余数为0，初始为1

    long long current = 0;
    long long ans = 0;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        current = (current + x) % n;
        if (current < 0) current += n;  // 处理负数情况
        cnt[current]++;
    }

    // 组合数学：每个余数贡献 C(cnt, 2) 个子数组
    for (long long x : cnt) {
        ans += x * (x - 1) / 2;
    }

    cout << ans << "\n";
    return 0;
}

时间复杂度: O(n)

---

总结

问题类型	解法	时间复杂度
多维前缀和（区间统计）	多维前缀和数组	O(1) 查询
静态区间求和	前缀和数组	O(1) 查询
子数组和为目标值（全正数）	滑动窗口	O(n)
子数组和为目标值（含负数）	哈希表	O(n)
子数组和为 k 的倍数（最长长度）	同余 + 首次出现位置	O(n)
子数组和为 n 的倍数（个数）	同余 + 组合数学	O(n)

核心思想: 前缀和将”区间求和”问题转化为”两点差”问题，结合哈希表或同余性质可以高效解决各类子数组求和问题。