万户网站天下企业咨询方案

在算法竞赛和日常的数据处理工作中，前缀和是一种极其重要的预处理技术。它能够在常数时间内回答多次区间查询，大大提高了算法效率。对于刚接触算法的新手来说，前缀和可能有些抽象，但只要掌握其核心思想和推导过程，就能轻松驾驭。接下来，本文将详细介绍一维前缀和和二维前缀和的原理、推导、实现以及应用场景。​

一、一维前缀和​

1. 基本概念​

一维前缀和的核心思想，是通过记录数组前 i 个元素的累加和，来快速计算数组中任意区间的和。我们以一个简单的数组 arr = [1, 3, 5, 7, 9] 为例，来详细推导前缀和数组的构建过程。​
前缀和数组 s 的定义为：​

• s[0] = arr[0]，在我们的例子中，s[0] = 1，即前缀和数组的第一个元素等于原数组的第一个元素。​
• 当i > 0时，s[i] = s[i - 1] + arr[i]。比如计算s[1]，根据公式，s[1] = s[0] + arr[1]，已知s[0] = 1，arr[1] = 3，所以s[1] = 1 + 3 = 4 ；继续计算s[2]，s[2] = s[1] + arr[2] = 4 + 5 = 9；以此类推，完整的前缀和数组 s 为 [1, 4, 9, 16, 25]。​

通过前缀和数组，我们就可以快速计算原数组中任意区间[i, j]的和。当i > 0时，区间和为s[j] - s[i - 1]，这是因为s[j]包含了从arr[0]到arr[j]的所有元素和，而s[i - 1]包含了从arr[0]到arr[i - 1]的所有元素和，两者相减，就得到了arr[i]到arr[j]的元素和；当i == 0时，区间和直接是s[j]，因为此时前缀和数组s[j]就是从原数组开头到arr[j]的所有元素和。​

2. C++ 代码实现​

下面是一维前缀和数组的 C++ 实现代码：

#include <iostream>
#include <vector>
using namespace std;// 计算一维前缀和数组
vector<int> calculatePrefixSum(const vector<int>& arr) {int n = arr.size();if (n == 0) return {};vector<int> prefixSum(n);prefixSum[0] = arr[0];for (int i = 1; i < n; ++i) {prefixSum[i] = prefixSum[i - 1] + arr[i];}return prefixSum;
}// 查询区间[i, j]的和
int queryRangeSum(const vector<int>& prefixSum, int i, int j) {if (i == 0) {return prefixSum[j];} else {return prefixSum[j] - prefixSum[i - 1];}
}int main() {// 示例数组vector<int> arr = {1, 3, 5, 7, 9};// 计算前缀和数组vector<int> prefixSum = calculatePrefixSum(arr);// 查询区间[1, 3]的和（对应原数组的第2到第4个元素）int sum = queryRangeSum(prefixSum, 1, 3);cout << "区间[1, 3]的和为: " << sum << endl; // 输出结果应为3 + 5 + 7 = 15return 0;
}

在 calculatePrefixSum 函数中，首先处理原数组为空的情况，然后初始化前缀和数组的第一个元素为原数组第一个元素，接着通过循环，根据前缀和公式依次计算出前缀和数组的其他元素。queryRangeSum函数则根据区间起始位置 i 是否为 0，选择不同的计算方式来返回区间和。

3. 应用场景​

一维前缀和的常见应用场景包括：​

• 频繁查询数组任意区间的和。例如在一个记录每天销售额的数组中，需要频繁查询某段时间内的总销售额，使用一维前缀和就能快速得出结果。​
• 快速计算数组子数组的和，用于解决子数组和相关问题。比如在一些算法题目中，要求找出和满足特定条件的子数组，前缀和可以帮助我们高效地计算子数组的和，从而快速筛选出符合条件的子数组。​
• 在统计和数据处理中，快速计算累积数据。如统计学生成绩的累计分数，通过前缀和可以快速得到每个学生及其之前学生的总成绩。

二、二维前缀和

1. 基本概念​

二维前缀和数组是一维前缀和在二维空间上的扩展，常用于快速计算二维数组中任意子矩阵的和。为了便于理解，我们以一个 3×3 的二维数组 matrix 为例进行推导，假设matrix为：

[[1, 2, 3],[4, 5, 6],[7, 8, 9]
]

二维前缀和数组 s 的定义为：s[i][j] 表示从原矩阵左上角 (0, 0) 到右下角 (i, j) 所构成的子矩阵中所有元素的和。​

其递推公式的推导过程如下：​

当i > 0且j > 0时，s[i][j] = matrix[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]。我们来分析这个公式，matrix[i][j] 是当前位置的元素；s[i - 1][j] 表示的是从左上角 (0, 0) 到 (i - 1, j) 的子矩阵和，它包含了当前位置左边所有元素的和；s[i][j - 1] 表示从左上角 (0, 0) 到 (i, j - 1) 的子矩阵和，它包含了当前位置上边所有元素的和；而 s[i - 1][j - 1] 在 s[i - 1][j] 和s[i][j - 1] 中都被计算了一次，即左上角 (0, 0) 到 (i - 1, j - 1) 的子矩阵和被重复计算了，所以要减去一次 s[i - 1][j - 1]，这样就能得到从左上角 (0, 0) 到右下角 (i, j) 的子矩阵和。​
对于边界情况，当 i == 0 且 j > 0 时，s[0][j] = s[0][j - 1] + matrix[0][j]，因为第一行没有上面的子矩阵，所以前缀和就是前一个位置的前缀和加上当前位置的元素；当 j == 0且 i > 0 时，s[i][0] = s[i - 1][0] + matrix[i][0]，同理，第一列没有左边的子矩阵，前缀和是前一个位置的前缀和加上当前位置的元素；当 i == 0 且 j == 0 时，s[0][0] = matrix[0][0]。
​
通过二维前缀和数组，我们可以在 O (1) 时间内计算出原矩阵中任意子矩阵 [(x1, y1), (x2, y2)] 的和。计算公式为：当 x1 > 0 且 y1 > 0 时，sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]。这个公式的原理和递推公式类似，s[x2][y2] 是包含目标子矩阵的大矩阵和，s[x1 - 1][y2] 和 s[x2][y1 - 1] 分别减去了目标子矩阵左边和上边多余的部分，但这样会导致左上角的子矩阵被多减了一次，所以要加上s[x1 - 1][y1 - 1] ；当x1 == 0 或 y1 == 0 时，按照类似的边界情况处理方式进行计算。

2. C++ 代码实现​

下面是二维前缀和数组的 C++ 实现代码：

#include <iostream>
#include <vector>
using namespace std;// 计算二维前缀和数组
vector<vector<int>> calculatePrefixSum2D(const vector<vector<int>>& matrix) {int rows = matrix.size();if (rows == 0) return {};int cols = matrix[0].size();vector<vector<int>> prefixSum(rows, vector<int>(cols, 0));// 初始化前缀和数组的第一行和第一列prefixSum[0][0] = matrix[0][0];// 初始化第一行for (int j = 1; j < cols; ++j) {prefixSum[0][j] = prefixSum[0][j - 1] + matrix[0][j];}// 初始化第一列for (int i = 1; i < rows; ++i) {prefixSum[i][0] = prefixSum[i - 1][0] + matrix[i][0];}// 填充剩余的前缀和数组for (int i = 1; i < rows; ++i) {for (int j = 1; j < cols; ++j) {prefixSum[i][j] = matrix[i][j] + prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1];}}return prefixSum;
}// 查询子矩阵[(x1, y1), (x2, y2)]的和（闭区间，包含四个端点）
int querySubmatrixSum(const vector<vector<int>>& prefixSum, int x1, int y1, int x2, int y2) {if (x1 == 0 && y1 == 0) {return prefixSum[x2][y2];} else if (x1 == 0) {return prefixSum[x2][y2] - prefixSum[x2][y1 - 1];} else if (y1 == 0) {return prefixSum[x2][y2] - prefixSum[x1 - 1][y2];} else {return prefixSum[x2][y2] - prefixSum[x1 - 1][y2] - prefixSum[x2][y1 - 1] + prefixSum[x1 - 1][y1 - 1];}
}int main() {// 示例二维数组vector<vector<int>> matrix = {{1, 2, 3},{4, 5, 6},{7, 8, 9}};// 计算二维前缀和数组vector<vector<int>> prefixSum = calculatePrefixSum2D(matrix);// 查询子矩阵[(1, 1), (2, 2)]的和（对应原矩阵的右下角2x2子矩阵）int sum = querySubmatrixSum(prefixSum, 1, 1, 2, 2);cout << "子矩阵[(1, 1), (2, 2)]的和为: " << sum << endl; // 输出结果应为5 + 6 + 8 + 9 = 28return 0;
}

在 calculatePrefixSum2D 函数中，先处理二维数组为空的情况，然后初始化二维前缀和数组，接着分别初始化第一行和第一列，最后通过两层循环，根据二维前缀和的递推公式填充整个前缀和数组。querySubmatrixSum 函数则根据子矩阵的起始位置是否在边界，选择不同的计算方式返回子矩阵的和。​

3. 应用场景​

二维前缀和的常见应用场景包括：​

• 频繁查询二维数组中任意子矩阵的和。比如在图像像素处理中，可能需要频繁计算图像中某个区域的像素总和，使用二维前缀和就能快速完成计算。​
• 图像处理中的区域像素和计算。除了求和，基于前缀和还可以计算区域的平均像素值等统计信息，为图像分析提供基础数据。​
• 地理信息系统中的区域统计分析。在地理信息系统中，将地图数据以二维数组形式存储，使用二维前缀和可以快速计算某个区域内的各种统计数据，如人口总数、土地面积总和等。​

三、总结​

前缀和是一种非常实用的预处理技术，通过构建前缀和数组，可以将区间和查询的时间复杂度从 O (n) 或 O (n²) 降低到 O (1)，大大提高了算法效率。无论是一维前缀和还是二维前缀和，理解其推导过程是掌握这项技术的关键。对于新手来说，建议多通过实际例子和练习题来加深对前缀和的理解和应用。希望本文对你理解前缀和算法有所帮助！如果你有任何疑问或建议，欢迎在评论区留言讨论。