C++前缀和与差分如何使用

目录

1. 引言
2. 前缀和的概念
3. 前缀和的应用
   • 一维前缀和
   • 二维前缀和
4. 差分的概念
5. 差分的应用
   • 一维差分
   • 二维差分
6. 前缀和与差分的结合使用
7. 实际应用案例
   • 案例1：区间求和
   • 案例2：区间更新
   • 案例3：二维区域求和
   • 案例4：二维区域更新
8. 总结

引言

在算法竞赛和实际编程中，前缀和与差分是两种非常常见且实用的技巧。它们主要用于处理数组或矩阵中的区间查询和区间更新问题。通过合理地使用前缀和与差分，我们可以将一些复杂的问题简化，从而提高算法的效率。本文将详细介绍前缀和与差分的概念、应用场景以及如何在C++中实现它们。

前缀和的概念

前缀和（Prefix Sum）是一种预处理技术，它通过计算数组中每个位置之前所有元素的和，来快速回答区间求和的问题。前缀和的核心思想是将区间求和问题转化为两个前缀和的差值问题。

一维前缀和

假设我们有一个一维数组 arr，其长度为 n。我们可以通过以下步骤来计算前缀和数组 prefix：

1. 初始化 prefix[0] = arr[0]。
2. 对于 i 从 1 到 n-1，计算 prefix[i] = prefix[i-1] + arr[i]。

通过这种方式，我们可以快速计算任意区间 [l, r] 的和，即 prefix[r] - prefix[l-1]（注意：当 l = 0 时，直接使用 prefix[r]）。

二维前缀和

对于二维数组 arr，其大小为 m x n，我们可以通过以下步骤来计算二维前缀和数组 prefix：

1. 初始化 prefix[0][0] = arr[0][0]。
2. 对于第一行和第一列，分别计算前缀和：
   • 对于 i 从 1 到 m-1，计算 prefix[i][0] = prefix[i-1][0] + arr[i][0]。
   • 对于 j 从 1 到 n-1，计算 prefix[0][j] = prefix[0][j-1] + arr[0][j]。
3. 对于其他位置 (i, j)，计算 prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + arr[i][j]。

通过这种方式，我们可以快速计算任意矩形区域 [x1, y1] 到 [x2, y2] 的和，即 prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1]。

差分的概念

差分（Difference）是前缀和的逆操作，它主要用于处理区间更新问题。差分的核心思想是通过记录每个位置的增量，来快速更新整个数组或矩阵。

一维差分

假设我们有一个一维数组 arr，其长度为 n。我们可以通过以下步骤来计算差分数组 diff：

1. 初始化 diff[0] = arr[0]。
2. 对于 i 从 1 到 n-1，计算 diff[i] = arr[i] - arr[i-1]。

通过这种方式，我们可以快速对任意区间 [l, r] 进行增量更新。假设我们要对区间 [l, r] 增加 val，我们只需要更新 diff[l] += val 和 diff[r+1] -= val（注意：当 r+1 超出数组范围时，不需要更新）。

二维差分

对于二维数组 arr，其大小为 m x n，我们可以通过以下步骤来计算二维差分数组 diff：

1. 初始化 diff[0][0] = arr[0][0]。
2. 对于第一行和第一列，分别计算差分：
   • 对于 i 从 1 到 m-1，计算 diff[i][0] = arr[i][0] - arr[i-1][0]。
   • 对于 j 从 1 到 n-1，计算 diff[0][j] = arr[0][j] - arr[0][j-1]。
3. 对于其他位置 (i, j)，计算 diff[i][j] = arr[i][j] - arr[i-1][j] - arr[i][j-1] + arr[i-1][j-1]。

通过这种方式，我们可以快速对任意矩形区域 [x1, y1] 到 [x2, y2] 进行增量更新。假设我们要对矩形区域 [x1, y1] 到 [x2, y2] 增加 val，我们只需要更新四个角的值： - diff[x1][y1] += val - diff[x1][y2+1] -= val - diff[x2+1][y1] -= val - diff[x2+1][y2+1] += val

前缀和与差分的结合使用

在实际应用中，前缀和与差分常常结合使用。例如，在处理区间更新和区间查询的问题时，我们可以先使用差分数组进行区间更新，然后再通过前缀和数组进行区间查询。

实际应用案例

案例1：区间求和

假设我们有一个一维数组 arr，我们需要频繁地查询任意区间 [l, r] 的和。我们可以通过以下步骤来实现：

1. 计算前缀和数组 prefix。
2. 对于每次查询 [l, r]，直接返回 prefix[r] - prefix[l-1]。

#include <iostream>
#include <vector>

using namespace std;

vector<int> prefixSum(const vector<int>& arr) {
    int n = arr.size();
    vector<int> prefix(n);
    prefix[0] = arr[0];
    for (int i = 1; i < n; ++i) {
        prefix[i] = prefix[i-1] + arr[i];
    }
    return prefix;
}

int rangeSum(const vector<int>& prefix, int l, int r) {
    if (l == 0) return prefix[r];
    return prefix[r] - prefix[l-1];
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};
    vector<int> prefix = prefixSum(arr);
    cout << "Sum from index 1 to 3: " << rangeSum(prefix, 1, 3) << endl; // Output: 9
    return 0;
}

案例2：区间更新

假设我们有一个一维数组 arr，我们需要频繁地对任意区间 [l, r] 进行增量更新。我们可以通过以下步骤来实现：

1. 计算差分数组 diff。
2. 对于每次更新 [l, r]，更新 diff[l] += val 和 diff[r+1] -= val。
3. 通过前缀和数组 prefix 来获取更新后的数组。

#include <iostream>
#include <vector>

using namespace std;

vector<int> differenceArray(const vector<int>& arr) {
    int n = arr.size();
    vector<int> diff(n);
    diff[0] = arr[0];
    for (int i = 1; i < n; ++i) {
        diff[i] = arr[i] - arr[i-1];
    }
    return diff;
}

void rangeUpdate(vector<int>& diff, int l, int r, int val) {
    diff[l] += val;
    if (r+1 < diff.size()) {
        diff[r+1] -= val;
    }
}

vector<int> getUpdatedArray(const vector<int>& diff) {
    int n = diff.size();
    vector<int> arr(n);
    arr[0] = diff[0];
    for (int i = 1; i < n; ++i) {
        arr[i] = arr[i-1] + diff[i];
    }
    return arr;
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};
    vector<int> diff = differenceArray(arr);
    rangeUpdate(diff, 1, 3, 2);
    vector<int> updatedArr = getUpdatedArray(diff);
    for (int num : updatedArr) {
        cout << num << " "; // Output: 1 4 5 6 5
    }
    cout << endl;
    return 0;
}

案例3：二维区域求和

假设我们有一个二维数组 arr，我们需要频繁地查询任意矩形区域 [x1, y1] 到 [x2, y2] 的和。我们可以通过以下步骤来实现：

1. 计算二维前缀和数组 prefix。
2. 对于每次查询 [x1, y1] 到 [x2, y2]，直接返回 prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1]。

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> prefixSum2D(const vector<vector<int>>& arr) {
    int m = arr.size();
    int n = arr[0].size();
    vector<vector<int>> prefix(m, vector<int>(n));
    prefix[0][0] = arr[0][0];
    for (int i = 1; i < m; ++i) {
        prefix[i][0] = prefix[i-1][0] + arr[i][0];
    }
    for (int j = 1; j < n; ++j) {
        prefix[0][j] = prefix[0][j-1] + arr[0][j];
    }
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + arr[i][j];
        }
    }
    return prefix;
}

int rangeSum2D(const vector<vector<int>>& prefix, int x1, int y1, int x2, int y2) {
    int sum = prefix[x2][y2];
    if (x1 > 0) sum -= prefix[x1-1][y2];
    if (y1 > 0) sum -= prefix[x2][y1-1];
    if (x1 > 0 && y1 > 0) sum += prefix[x1-1][y1-1];
    return sum;
}

int main() {
    vector<vector<int>> arr = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    vector<vector<int>> prefix = prefixSum2D(arr);
    cout << "Sum from (1,1) to (2,2): " << rangeSum2D(prefix, 1, 1, 2, 2) << endl; // Output: 28
    return 0;
}

案例4：二维区域更新

假设我们有一个二维数组 arr，我们需要频繁地对任意矩形区域 [x1, y1] 到 [x2, y2] 进行增量更新。我们可以通过以下步骤来实现：

1. 计算二维差分数组 diff。
2. 对于每次更新 [x1, y1] 到 [x2, y2]，更新四个角的值：
   • diff[x1][y1] += val
   • diff[x1][y2+1] -= val
   • diff[x2+1][y1] -= val
   • diff[x2+1][y2+1] += val
3. 通过二维前缀和数组 prefix 来获取更新后的数组。

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> differenceArray2D(const vector<vector<int>>& arr) {
    int m = arr.size();
    int n = arr[0].size();
    vector<vector<int>> diff(m, vector<int>(n));
    diff[0][0] = arr[0][0];
    for (int i = 1; i < m; ++i) {
        diff[i][0] = arr[i][0] - arr[i-1][0];
    }
    for (int j = 1; j < n; ++j) {
        diff[0][j] = arr[0][j] - arr[0][j-1];
    }
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            diff[i][j] = arr[i][j] - arr[i-1][j] - arr[i][j-1] + arr[i-1][j-1];
        }
    }
    return diff;
}

void rangeUpdate2D(vector<vector<int>>& diff, int x1, int y1, int x2, int y2, int val) {
    diff[x1][y1] += val;
    if (y2+1 < diff[0].size()) {
        diff[x1][y2+1] -= val;
    }
    if (x2+1 < diff.size()) {
        diff[x2+1][y1] -= val;
    }
    if (x2+1 < diff.size() && y2+1 < diff[0].size()) {
        diff[x2+1][y2+1] += val;
    }
}

vector<vector<int>> getUpdatedArray2D(const vector<vector<int>>& diff) {
    int m = diff.size();
    int n = diff[0].size();
    vector<vector<int>> arr(m, vector<int>(n));
    arr[0][0] = diff[0][0];
    for (int i = 1; i < m; ++i) {
        arr[i][0] = arr[i-1][0] + diff[i][0];
    }
    for (int j = 1; j < n; ++j) {
        arr[0][j] = arr[0][j-1] + diff[0][j];
    }
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            arr[i][j] = arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1] + diff[i][j];
        }
    }
    return arr;
}

int main() {
    vector<vector<int>> arr = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    vector<vector<int>> diff = differenceArray2D(arr);
    rangeUpdate2D(diff, 1, 1, 2, 2, 2);
    vector<vector<int>> updatedArr = getUpdatedArray2D(diff);
    for (const auto& row : updatedArr) {
        for (int num : row) {
            cout << num << " ";
        }
        cout << endl;
    }
    // Output:
    // 1 2 3
    // 4 7 8
    // 7 10 11
    return 0;
}

总结

前缀和与差分是处理区间查询和区间更新问题的强大工具。通过合理地使用它们，我们可以将一些复杂的问题简化，从而提高算法的效率。在实际应用中，前缀和与差分常常结合使用，特别是在需要频繁进行区间更新和区间查询的场景中。希望本文的介绍能够帮助读者更好地理解和应用前缀和与差分技术。