C++ 算法技巧 — 前缀和 (Prefix Sum)

章节概述

前缀和是一种预处理技术，通过 O(n) 预处理后实现 O(1) 区间求和，是优化暴力累加的核心手段。

核心原理

1. 一维前缀和 — 差分消去

给定数组 $a [1.. n]$ ，定义前缀和数组：
$p r e [i] = a [1] + a [2] + \dots + a [i]$

递推公式: $p r e [i] = p r e [i - 1] + a [i]$ ，其中 $p r e [0] = 0$

区间求和: $s u m [l .. r] = p r e [r] - p r e [l - 1]$

数学原理:  pre[r] = a[1]+...+a[l-1] + a[l]+...+a[r] = pre[l-1] + sum[l..r]
=> sum[l..r] = pre[r] - pre[l-1]

2. 二维前缀和 — 容斥原理

给定矩阵 $a [1.. n] [1.. m]$ ，定义：
$p r e [i] [j] = \sum_{x = 1}^{i} \sum_{y = 1}^{j} a [x] [y]$

递推公式:
$p r e [i] [j] = p r e [i - 1] [j] + p r e [i] [j - 1] - p r e [i - 1] [j - 1] + a [i] [j]$

子矩阵求和 (矩形 (x1,y1) 到 (x2,y2)):
$s u m = p r e [x 2] [y 2] - p r e [x 1 - 1] [y 2] - p r e [x 2] [y 1 - 1] + p r e [x 1 - 1] [y 1 - 1]$

3. 前缀和的扩展应用

变体	说明	典型问题
前缀异或	$p r e X or [i] = a [1] \oplus \dots \oplus a [i]$	区间异或为 0
模前缀和	$p r e M o d [i] = (p r e [i] mod k)$	和能被 k 整除的子数组
前缀最值	$p r e M a x [i] = max (a [1], ..., a [i])$	前后缀分解

关键数据结构

A_容器_Container — vector 存储前缀和数组 (O(n) 空间)

一维前缀和

给定数组 a[1..n]，定义前缀和数组 pre[i] = a[1] + a[2] + … + a[i]。

递推公式: pre[i] = pre[i-1] + a[i]，其中 pre[0] = 0。

区间求和: sum[l..r] = pre[r] - pre[l-1]

#include <iostream>
using namespace std;
const int N = 100005;
int a[N], pre[N];
 
int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << pre[r] - pre[l - 1] << endl;
    }
    return 0;
}

二维前缀和

给定矩阵 a[1..n][1..m]，定义 pre[i][j] = 以 (1,1) 为左上角、(i,j) 为右下角的子矩阵元素和。

递推公式: pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j]

子矩阵求和: sum = pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1]

#include <iostream>
using namespace std;
const int N = 1005;
int a[N][N], pre[N][N];
 
int main() {
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            pre[i][j] = pre[i-1][j] + pre[i][j-1]
                      - pre[i-1][j-1] + a[i][j];
        }
    while (q--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        int ans = pre[x2][y2] - pre[x1-1][y2]
                - pre[x2][y1-1] + pre[x1-1][y1-1];
        cout << ans << endl;
    }
    return 0;
}

P5638 光骓者的荣耀

题目: 一条长度为 n 的道路，第 i 段需要时间 a[i]。传送器可以跳过恰好 k 段连续道路。求从起点到终点的最短时间。

思路: 前缀和维护道路总时间。枚举传送器的起始位置，被跳过的 k 段时间和 = pre[i+k-1] - pre[i-1]，
答案 = 总时间 - 最大可跳过时间。

#include <iostream>
using namespace std;
const int N = 1000005;
long long a[N], pre[N];
 
int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    long long maxSkip = 0;
    for (int i = 1; i + k - 1 < n; i++) {
        long long skip = pre[i + k - 1] - pre[i - 1];
        if (skip > maxSkip) maxSkip = skip;
    }
    cout << pre[n - 1] - maxSkip << endl;
    return 0;
}

P3131 [USACO16JAN] Subsequences Summing to Sevens

题目: N 头牛排成一行，每头牛有一个编号 ID。求一个连续区间，使得编号之和能被 7 整除，且区间最长。

思路: pre[i] 表示前 i 头牛编号之和。若 pre[r] ≡ pre[l-1] (mod 7)，则区间 [l,r] 的和能被 7 整除。
记录每个 mod 值最早出现的位置。

#include <iostream>
using namespace std;
const int N = 50005;
int first[7];
 
int main() {
    int n, sum = 0, ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        sum = (sum + x) % 7;
        if (first[sum] == 0 && sum != 0)
            first[sum] = i;
        else if (i - first[sum] > ans)
            ans = i - first[sum];
    }
    cout << ans << endl;
    return 0;
}

RootStack

探索

C++ 算法技巧 — 前缀和 (Prefix Sum)

章节概述

核心原理

关键数据结构

一维前缀和

二维前缀和

P5638 光骓者的荣耀

P3131 [USACO16JAN] Subsequences Summing to Sevens

推荐练习题（洛谷）

相关技巧

多平台练习

关系图谱

目录

反向链接