首页 书籍 深入浅出程序设计竞赛(进阶篇)

前缀和是一种重要的数据预处理技术，它可以极大地优化对数组或矩阵中连续子数组（或子矩阵）求和的操作。通过预先计算并存储到某个位置为止的元素总和，前缀和能够让我们在 O (1) 的时间内快速计算出任意连续子数组的和，这对于解决一些需要频繁进行区间求和的问题非常有效。

# 一维前缀和

对于一个给定的数组 arr ，其前缀和数组 prefixSum 可以这样计算： prefixSum[i] 表示 arr 数组中从第 0 个元素到第 i 个元素的总和。具体来说， prefixSum[0] = arr[0] ，对于所有的 i > 0 ， prefixSum[i] = prefixSum[i-1] + arr[i] 。

# 示例代码：

#include <iostream>
#include <vector>
using namespace std;
vector<int> computePrefixSum(const vector<int>& nums) {
    int n = nums.size();
    vector<int> prefixSum(n, 0);
    prefixSum[0] = nums[0];
    for (int i = 1; i < n; ++i) {
        prefixSum[i] = prefixSum[i - 1] + nums[i];
    }
    return prefixSum;
}
// 使用前缀和计算区间 [l, r] 内的元素总和
int rangeSum(const vector<int>& prefixSum, int l, int r) {
    if (l == 0) return prefixSum[r];
    return prefixSum[r] - prefixSum[l - 1];
}
int main() {
    vector<int> nums = {3, 1, 2, 5, 4};
    vector<int> prefixSum = computePrefixSum(nums);
    cout << "Sum of range [1, 3]: " << rangeSum(prefixSum, 1, 3) << endl; // 输出：8
    return 0;
}
# 二维前缀和


二维前缀和是一维前缀和的扩展，用于处理矩阵中的子矩阵求和问题。对于一个二维矩阵 matrix ，其二维前缀和 prefixSum  可以定义为： prefixSum[i][j]  表示原矩阵中从 (0, 0)  到 (i, j)  形成的子矩阵的元素总和。


# 示例代码：


#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> compute2DPrefixSum(const vector<vector<int>>& matrix) {
    int rows = matrix.size();
    int cols = matrix[0].size();
    vector<vector<int>> prefixSum(rows, vector<int>(cols, 0));
    prefixSum[0][0] = matrix[0][0];
    // 初始化第一行和第一列
    for (int i = 1; i < rows; ++i) {
        prefixSum[i][0] = prefixSum[i - 1][0] + matrix[i][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) {
        for (int j = 1; j < cols; ++j) {
            prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + matrix[i][j];
        }
    }
    return prefixSum;
}
// 使用二维前缀和计算子矩阵的元素总和
int matrixRangeSum(const vector<vector<int>>& prefixSum, int x1, int y1, int x2, int y2) {
    int sum = prefixSum[x2][y2];
    if (x1 > 0) sum -= prefixSum[x1 - 1][y2];
    if (y1 > 0) sum -= prefixSum[x2][y1 - 1];
    if (x1 > 0 && y1 > 0) sum += prefixSum[x1 - 1][y1 - 1];
    return sum;
}
int main() {
    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}
    };
    vector<vector<int>> prefixSum = compute2DPrefixSum(matrix);
    cout << "Sum of submatrix [(1, 1), (2, 2)]: " << matrixRangeSum(prefixSum, 1, 1, 2, 2) << endl; // 输出：11
    return 0;
}
通过使用前缀和技术，我们能够将一些看似复杂的区间求和或子矩阵求和问题转化为简单的数学计算，从而显著提高算法的效率。


      

          
          
      

  


   


    

  
    
      
    
    更新于