我的算法书 - 前缀和

一句话算法

前缀和先记住“从开头到当前位置的总和”，查询区间时用右端总和减掉左端前面的总和。

问题模型

给定一个长度为 $n$ 的数组 $a_1,a_2,\dots,a_n$ 。数组不会修改，有 $q$ 次询问，每次给出区间 $[l,r]$ ，要求快速求：

\sum_{i=l}^{r} a_i

如果每次询问都从 $l$ 加到 $r$ ，一次查询最坏需要 $O(n)$ 。当前缀和预处理完成后，每次查询只需要一次减法，复杂度变成 $O(1)$ 。

核心直觉

把数组想成一条从左到右累加的账本。

s[r] 记录从第 $1$ 个数到第 $r$ 个数的总和，s[l-1] 记录区间左边那一段不需要的总和。把左边多算的部分减掉，剩下的就是 $[l,r]$ 。

例如要求 $a_3+a_4+a_5$ ：

\begin{aligned} s_5 &= a_1+a_2+a_3+a_4+a_5 \\ s_2 &= a_1+a_2 \\ s_5-s_2 &= a_3+a_4+a_5 \end{aligned}

所以一般地：

\sum_{i=l}^{r} a_i = s_r - s_{l-1}

为了让 $l=1$ 时也能统一处理，通常定义 $s_0=0$ 。

算法步骤

令 s[0] = 0。
从左到右扫描数组，计算 s[i] = s[i - 1] + a[i]。
对每个询问 [l, r]，直接返回 s[r] - s[l - 1]。

注意：文章里的公式使用 $1$ 下标，模板代码中原数组用 0 下标存储，前缀和数组 s 仍然按“前几个数”理解。

算法证明

核心不变量： $s_i$ 永远表示前 $i$ 个元素的和。

定义
$s_i=a_1+a_2+\cdots+a_i$
拆开右端前缀
$s_r=a_1+\cdots+a_{l-1}+a_l+\cdots+a_r$
拆开左端前面的前缀
$s_{l-1}=a_1+\cdots+a_{l-1}$
相减抵消
$s_r-s_{l-1}=a_l+\cdots+a_r$

所以 query(l, r) = s[r] - s[l - 1] 正确。

复杂度分析

预处理时间复杂度： $O(n)$ 。
单次查询时间复杂度： $O(1)$ 。
空间复杂度： $O(n)$ ，用于保存前缀和数组。

如果数值和可能超过 int，应使用 long long。

代码实现

一维前缀和

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

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

using ll = long long;

struct PrefixSum {
    vector<ll> s;

    PrefixSum() = default;

    explicit PrefixSum(const vector<ll>& a) {
        init(a);
    }

    // a 使用 0 下标存储，s[i] 表示前 i 个数的和。
    void init(const vector<ll>& a) {
        int n = (int)a.size();
        s.assign(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + a[i - 1];
        }
    }

    // 查询 1 下标闭区间 [l, r] 的区间和。
    ll query(int l, int r) const {
        return s[r] - s[l - 1];
    }
};

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

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

    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    PrefixSum ps(a);

    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << ps.query(l, r) << '\n';
    }

    return 0;
}

二维前缀和 Python

二维前缀和的查询公式来自容斥：

sum(x_1,y_1,x_2,y_2) =s[x_2][y_2]-s[x_1-1][y_2]-s[x_2][y_1-1]+s[x_1-1][y_1-1]

模板中坐标使用 $1$ 下标闭区间。

python

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

        import sys
from itertools import accumulate


input = sys.stdin.buffer.readline


def build_prefix(n, m):
    prefix = [[0] * (m + 1)]

    for _ in range(n):
        row_prefix = accumulate(map(int, input().split()), initial=0)
        prefix.append([up + left for up, left in zip(prefix[-1], row_prefix)])

    return prefix


def rect_sum(prefix, x1, y1, x2, y2):
    return (
        prefix[x2][y2]
        - prefix[x1 - 1][y2]
        - prefix[x2][y1 - 1]
        + prefix[x1 - 1][y1 - 1]
    )


def main():
    first = input().split()
    if not first:
        return

    n, m, q = map(int, first)
    prefix = build_prefix(n, m)

    answer = []
    for _ in range(q):
        x1, y1, x2, y2 = map(int, input().split())
        answer.append(str(rect_sum(prefix, x1, y1, x2, y2)))

    sys.stdout.write("\n".join(answer))


if __name__ == "__main__":
    main()

测试用例

输入：

输出：

7
15
7

解释：

$[1,3]$ 的和是 $2+1+4=7$ 。
$[2,5]$ 的和是 $1+4+7+3=15$ 。
$[4,4]$ 的和是 $7$ 。

应用分类详解

前缀和的本质是：把“区间贡献”转成“两个前缀状态的差”。只要一个问题能把连续区间的信息表示成右端状态减左端状态，就应该想到前缀和。

一、静态区间和查询

典型模式： 数组不修改，频繁询问连续区间的和。

识别信号： 题面出现“多次询问”“区间 $[l,r]$ ”“求和”“原数组不变”。

核心建模： 预处理 s[i] 表示前 $i$ 个元素的和，查询时用 s[r] - s[l - 1]。

应用场景	经典题目	核心思路
区间和模板	luogu-P8218	预处理一次，之后每次询问 $O(1)$
子段贡献统计	luogu-P3131	前缀和结合取模，统计同余前缀

二、寻找满足条件的连续子数组

典型模式： 问某个连续子数组是否满足“和等于/能被整除/达到某个值”。

识别信号： 题面强调“连续子数组”“subarray”“区间和等于 $k$ ”“区间和能被 $m$ 整除”。

核心建模： 设区间 $[l,r]$ 的和为 s[r] - s[l - 1]。问题会变成寻找两个前缀状态之间的关系。

应用场景	经典题目	核心思路
中心下标	LeetCode 724	左侧和等于总和减左侧和减当前值
连续子数组和	LeetCode 523	若两个前缀和模 $k$ 相同，中间区间和能被 $k$ 整除

三、二维前缀和

典型模式： 在矩阵中多次查询子矩形的和。

识别信号： 题面出现“矩阵”“子矩形”“左上角/右下角”“多次询问面积内总和”。

核心建模： s[i][j] 表示左上角 (1,1) 到 (i,j) 的矩形和。查询一个子矩形时，用大矩形减掉上方和左方，再把左上角被多减的部分加回来。

如果题目要求在矩阵中寻找固定边长 side 的最大子方阵，可以枚举每个左上角 (x,y)，再用二维前缀和 $O(1)$ 求：

python

        1

        total = rect_sum(prefix, x, y, x + side - 1, y + side - 1)

应用场景	经典题目	核心思路
最大子矩阵	luogu-P1719	枚举行边界后用前缀和快速求子矩形和

四、前缀状态计数

典型模式： 不只查询一个固定区间，而是统计有多少个区间满足某种条件。

识别信号： 题面问“有多少个连续区间”“多少个子数组”“区间和对某数取模为某值”。

核心建模： 每个区间都对应一对前缀。统计区间数量，常常变成统计此前出现过多少个匹配的前缀状态。

应用场景	经典题目	核心思路
模意义下的区间和	luogu-P3131	`s[r] % m == s[l-1] % m` 时，中间区间和是 $m$ 的倍数
指定和子数组数量	LeetCode 560	统计此前出现过多少个 `s[i] - k`

经典例题

1. luogu-P8218

这是前缀和最直接的模板题。数组不修改，多次询问区间和，直接预处理 s[i]，每次输出 s[r] - s[l - 1]。

2. luogu-P3131

要求寻找和能被 $7$ 整除的最长连续区间。若两个前缀和对 $7$ 的余数相同，那么它们之间的区间和就是 $7$ 的倍数。记录每个余数最早和最晚出现的位置即可。

3. LeetCode 523 连续的子数组和

这是“前缀和 + 同余”的典型题。扫描前缀和，对每个余数只保留最早出现的位置，若同一个余数再次出现且距离至少为 $2$ ，就存在满足条件的连续子数组。

4. luogu-P1719

二维前缀和的经典应用。先用二维前缀和 $O(1)$ 求任意子矩形和，再枚举子矩形边界，得到最大子矩阵和。

参考

旧版文章：Rbook_ejs_old/book/base/presum/index.md
旧版模板：Rbook_ejs_old/algo_template/base/presum.cpp