01_前缀和

前缀和

前缀和模板

# 一维前缀和
prefix = [0] * (n + 1)
for i in range(n):
  prefix[i + 1] = prefix[i] + a[i]  # a 是 0-indexed

# 查询区间 [l, r]（1-indexed）
def query(l, r):
  return prefix[r] - prefix[l - 1]

# 二维前缀和
prefix = [[0] * (m+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        prefix[i][j] = grid[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]

Python 实现：一维前缀和可直接用 itertools.accumulate，前缀最值、前缀积、后缀数组也是一行——用法详见 07_Python工具函数 。

---

什么是前缀和？

用途：快速求区间和，查询时间 O(1)，预处理 O(n)

原理：prefix[i] 表示前 i 个元素的和，区间 [l, r] 的和 = prefix[r] - prefix[l-1]

前缀和（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]$$

---

经典例题

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

来源：USACO - Breed Counting

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

思路：多维前缀和

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

import sys

def main():
    # 使用文件输入输出
    sys.stdin = open("bcount.in", "r")
    sys.stdout = open("bcount.out", "w")

    data = sys.stdin.read().split()
    idx = 0

    n = int(data[idx]); idx += 1
    q = int(data[idx]); idx += 1

    # 三个前缀和数组
    pref1 = [0] * (n + 1)
    pref2 = [0] * (n + 1)
    pref3 = [0] * (n + 1)

    for i in range(1, n + 1):
        # 先复制前一个位置的值
        pref1[i] = pref1[i - 1]
        pref2[i] = pref2[i - 1]
        pref3[i] = pref3[i - 1]

        x = int(data[idx]); idx += 1
        if x == 1:
            pref1[i] += 1      # 品种1：Holsteins
        elif x == 2:
            pref2[i] += 1      # 品种2：Guernseys
        else:                  # x == 3
            pref3[i] += 1      # 品种3：Jerseys

    out = []
    for _ in range(q):
        l = int(data[idx]); idx += 1
        r = int(data[idx]); idx += 1
        # 区间 [l, r] 的各品种数量 = 前缀差
        out.append(f"{pref1[r] - pref1[l - 1]} "
                   f"{pref2[r] - pref2[l - 1]} "
                   f"{pref3[r] - pref3[l - 1]}")

    sys.stdout.write("\n".join(out) + "\n")

if __name__ == "__main__":
    main()

复杂度：- 预处理：O(n)

• 单次查询：O(1)
• 总时间：O(n + q)

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

来源：USACO - Div7

给定 n 个数，求和为 7 的倍数的子数组的最长长度。

核心原理：同余定理

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

思路：1. 记录每个余数首次出现的下标

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

import sys

def main():
    # 重定向标准输入输出到文件（对应 C++ 的 freopen）
    sys.stdin = open("div7.in", "r")
    sys.stdout = open("div7.out", "w")

    # 一次性读入所有数据，提高效率
    data = sys.stdin.read().split()
    idx = 0

    n = int(data[idx]); idx += 1

    # 记录每个余数首次出现的下标，-1 表示未出现
    first_idx = [-1] * 7
    first_idx[0] = 0  # 前缀和为 0 时，下标为 0

    current_sum = 0
    max_length = 0

    for i in range(1, n + 1):
        x = int(data[idx]); idx += 1
        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])

    sys.stdout.write(str(max_length) + "\n")

if __name__ == "__main__":
    main()

复杂度：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)

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