当前没有测试数据。

你好！我是你的OI竞赛教练。

Labuladong 的这篇文章非常经典，核心讲解了如何利用预处理将“区间求和”的时间复杂度从 $O(N)$ 降至 $O(1)$。这在通过时间限制严格的测试点时至关重要。（本质是空间换时间！空间复杂度增加了，降低了时间复杂度。但OI比赛一般是对时间复杂度要求更严格）

以下是为你整理的 OI 竞赛风格课件，完全涵盖了原文关于一维和二维前缀和的所有知识点。

---

OI 专题课件：前缀和技巧 (Prefix Sum)

1. 核心思想与适用场景

• 核心思想：通过 $O(N)$ 的预处理，记录从起点到当前位置的累加和，从而实现 $O(1)$ 时间复杂度的区间查询。
• 适用场景：
  1. 原始数组不会被修改（静态数组）。
  2. 需要频繁查询某个区间的累加和。
• 对比：如果数组需要频繁修改（区间加减），则需要使用“差分数组”或“线段树/树状数组”。

---

2. 一维前缀和 (1D Prefix Sum)

2.1 原理推导

假设原数组为 nums（长度为 $N$）。 我们需要查询索引 [left, right] 闭区间的和。

• 暴力法：遍历 left 到 right，时间复杂度 $O(N)$。如果查询 $M$ 次，总复杂度 $O(MN)$，容易 TLE。

• 前缀和法： 定义 preSum[i] 表示 nums 中前 i 个元素的和（即 nums[0..i-1] 的和）。

  • preSum[0] = 0 (为了方便计算，通常多开一个空间)
  • preSum[1] = nums[0]
  • preSum[i] = preSum[i-1] + nums[i-1]

  查询公式： nums[left..right] 的和 = preSum[right+1] - preSum[left]

2.2 OI 风格代码实现 (C++14)

/**
 * 知识点：一维前缀和
 * 题目模型：给定数组，多次询问区间 [L, R] 的和
 */
#include <vector>
#include <iostream>

using namespace std;

class PrefixSum1D {
private:
    // preSum[i] 存储 nums[0...i-1] 的和
    vector<long long> preSum; // 教练提示：涉及求和，防爆int，习惯用 long long

public:
    // 构造函数：O(N) 预处理
    PrefixSum1D(const vector<int>& nums) {
        int n = nums.size();
        // 技巧：多申请一个空间，preSum[0] = 0，避免处理边界问题
        preSum.resize(n + 1);
        preSum[0] = 0; 
        for (int i = 1; i <= n; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
    }

    // 查询函数：O(1)
    // 查询闭区间 [left, right] 的累加和
    long long query(int left, int right) {
        // 根据定义:
        // preSum[right+1] 是 nums[0..right] 的和
        // preSum[left]    是 nums[0..left-1] 的和
        // 相减即为 nums[left..right]
        return preSum[right + 1] - preSum[left];
    }
};

// 模拟 OI 测试主程序
int main() {
    // 优化 I/O 效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 示例输入：数组大小 5，查询 2 次
    // 数组：-2 0 3 -5 2
    vector<int> nums = {-2, 0, 3, -5, 2};
    
    PrefixSum1D solver(nums);
    
    // 样例查询
    cout << solver.query(0, 2) << "\n"; // nums[0..2] = -2+0+3 = 1
    cout << solver.query(2, 4) << "\n"; // nums[2..4] = 3-5+2 = 0
    cout << solver.query(0, 4) << "\n"; // nums[0..4] = -2

    return 0;
}

---

3. 二维前缀和 (2D Prefix Sum)

3.1 原理推导 (容斥原理)

对于二维矩阵 matrix，我们需要查询子矩阵（左上角 (r1, c1) 到右下角 (r2, c2)）的所有元素之和。

定义：preSum[i][j] 表示从矩阵左上角 (0, 0) 到 (i-1, j-1) 这个矩形区域内所有元素的和。

第一步：如何构造 preSum 数组？

我们需要利用已知的左边、上边的和，加上当前元素，减去重叠部分。

$$preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + matrix[i-1][j-1] $$

(图解提示：当前面积 = 上方矩形 + 左方矩形 - 左上角重叠矩形 + 当前小格子)

第二步：如何查询子矩阵和？

要计算红色目标区域 (r1, c1) 到 (r2, c2) 的和，可以使用大矩形减去多余部分：

$$Sum = preSum[r2+1][c2+1] - preSum[r1][c2+1] - preSum[r2+1][c1] + preSum[r1][c1] $$

(图解提示：目标面积 = 右下角大矩形 - 只有上边的矩形 - 只有左边的矩形 + 左上角被多减了一次的矩形)

3.2 OI 风格代码实现 (C++14)

/**
 * 知识点：二维前缀和
 * 题目模型：给定二维矩阵，多次询问子矩阵的和
 */
#include <vector>
#include <iostream>

using namespace std;

class PrefixSum2D {
private:
    // preSum[i][j] 记录矩阵 (0,0) 到 (i-1, j-1) 的元素和
    vector<vector<long long>> preSum;

public:
    // 构造函数：O(N*M) 预处理
    PrefixSum2D(const vector<vector<int>>& matrix) {
        int m = matrix.size();
        if (m == 0) return;
        int n = matrix[0].size();

        // 技巧：行列都多申请一个空间，初始化为 0
        preSum = vector<vector<long long>>(m + 1, vector<long long>(n + 1, 0));

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 核心构造公式：上 + 左 - 左上重叠 + 当前值
                // 注意 matrix 下标需要减 1
                preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] 
                             - preSum[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }

    // 查询函数：O(1)
    // 查询左上角 (row1, col1) 到右下角 (row2, col2) 的子矩阵和
    long long query(int row1, int col1, int row2, int col2) {
        // 核心查询公式：右下 - 上 - 左 + 左上重叠
        // 同样注意下标转换，row2+1 代表包含 row2 行
        return preSum[row2 + 1][col2 + 1] 
             - preSum[row1][col2 + 1] 
             - preSum[row2 + 1][col1] 
             + preSum[row1][col1];
    }
};

// 模拟 OI 测试主程序
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 示例矩阵
    vector<vector<int>> matrix = {
        {3, 0, 1, 4, 2},
        {5, 6, 3, 2, 1},
        {1, 2, 0, 1, 5},
        {4, 1, 0, 1, 7},
        {1, 0, 3, 0, 5}
    };

    PrefixSum2D solver(matrix);

    // 样例 1: 左上(2,1) 到 右下(4,3)
    // 包含行 2,3,4；列 1,2,3
    // 2, 0, 1
    // 1, 0, 1
    // 0, 3, 0
    // Sum = 8
    cout << solver.query(2, 1, 4, 3) << "\n";

    return 0;
}

---

4. 教练总结与记忆口诀

4.1 关键点

1. 空间换时间：多开一个辅助数组，查询飞快。
2. 下标偏移：preSum 长度设为 N+1，preSum[i] 对应原数组前 i 个项。这样做可以避免 i-1 < 0 的边界判断，代码更简洁。
3. 数据类型：累加和很容易超过 int 范围（$2 \times 10^9$），在 OI 竞赛中，前缀和数组建议一律使用 long long。

4.2 记忆口诀

• 一维构造：前加今 (pre[i-1] + nums[i])
• 一维查询：尾减头 (pre[R+1] - pre[L])
• 二维构造：上加左，减重叠，加自己。
• 二维查询：大减左，减去上，加回左上角。

---

5. 课后练习 (LeetCode 对应题目)

1. 303. 区域和检索 - 数组不可变 (一维前缀和模板)
2. 304. 二维区域和检索 - 矩阵不可变 (二维前缀和模板)