当前位置：首页 > article >正文

一维二维前缀和、差分，c++

article 2025/2/1 7:40:30

前缀和（Prefix Sum）是一种常用的预处理技术，用于快速计算数组中任意区间的和。前缀和的核心思想是通过预处理，将区间和的查询时间复杂度从 (O(n)) 降低到 (O(1))。

以下是前缀和的模板和示例：

1. 一维前缀和

1.1 模板

#include <iostream>
#include <vector>

// 计算前缀和
std::vector<int> computePrefixSum(const std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> prefix(n + 1, 0); // prefix[0] = 0

    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + nums[i - 1];
    }

    return prefix;
}

// 查询区间和
int queryRangeSum(const std::vector<int>& prefix, int l, int r) {
    return prefix[r + 1] - prefix[l];
}

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5};

    // 计算前缀和
    std::vector<int> prefix = computePrefixSum(nums);

    // 查询区间和
    int sum1 = queryRangeSum(prefix, 1, 3); // 2 + 3 + 4 = 9
    int sum2 = queryRangeSum(prefix, 0, 4); // 1 + 2 + 3 + 4 + 5 = 15

    std::cout << "Sum of [1, 3]: " << sum1 << std::endl;
    std::cout << "Sum of [0, 4]: " << sum2 << std::endl;

    return 0;
}

输出：

Sum of [1, 3]: 9
Sum of [0, 4]: 15

1.2 应用场景

区间和查询：快速计算任意区间的和。
差分数组：结合差分数组，可以高效处理区间更新操作。

2. 二维前缀和

2.1 模板

#include <iostream>
#include <vector>

// 计算二维前缀和
std::vector<std::vector<int>> compute2DPrefixSum(const std::vector<std::vector<int>>& matrix) {
    int rows = matrix.size();
    int cols = matrix[0].size();

    std::vector<std::vector<int>> prefix(rows + 1, std::vector<int>(cols + 1, 0));

    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + matrix[i - 1][j - 1];
        }
    }

    return prefix;
}

// 查询子矩阵和
int querySubmatrixSum(const std::vector<std::vector<int>>& prefix, int x1, int y1, int x2, int y2) {
    return prefix[x2 + 1][y2 + 1] - prefix[x1][y2 + 1] - prefix[x2 + 1][y1] + prefix[x1][y1];
}

int main() {
    std::vector<std::vector<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    // 计算二维前缀和
    auto prefix = compute2DPrefixSum(matrix);

    // 查询子矩阵和
    int sum1 = querySubmatrixSum(prefix, 0, 0, 1, 1); // 1 + 2 + 4 + 5 = 12
    int sum2 = querySubmatrixSum(prefix, 1, 1, 2, 2); // 5 + 6 + 8 + 9 = 28

    std::cout << "Sum of submatrix [0,0] to [1,1]: " << sum1 << std::endl;
    std::cout << "Sum of submatrix [1,1] to [2,2]: " << sum2 << std::endl;

    return 0;
}

输出：

Sum of submatrix [0,0] to [1,1]: 12
Sum of submatrix [1,1] to [2,2]: 28

2.2 应用场景

子矩阵和查询：快速计算任意子矩阵的和。
图像处理：用于计算图像中某个区域的总和或平均值。

3. 前缀和与差分数组的结合

3.1 差分数组模板

差分数组是前缀和的逆操作，用于高效处理区间更新。

#include <iostream>
#include <vector>

// 区间更新
void rangeUpdate(std::vector<int>& diff, int l, int r, int val) {
    diff[l] += val;
    if (r + 1 < diff.size()) {
        diff[r + 1] -= val;
    }
}

// 获取最终数组
std::vector<int> getFinalArray(const std::vector<int>& diff) {
    std::vector<int> result(diff.size() - 1, 0);
    result[0] = diff[0];
    for (int i = 1; i < result.size(); i++) {
        result[i] = result[i - 1] + diff[i];
    }
    return result;
}

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5};
    std::vector<int> diff(nums.size() + 1, 0);

    // 区间更新
    rangeUpdate(diff, 1, 3, 10); // 对 [1, 3] 区间加 10

    // 获取最终数组
    auto result = getFinalArray(diff);

    // 输出结果
    std::cout << "Final Array: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}