c++中差分以及前缀和代码分享

前缀和

前缀和是一种将区间求和问题转化为常数时间查询的技巧。通过预处理一个数组，计算数组中每个元素之前所有元素的和，可以快速进行区间求和。

前缀和的计算：
我们可以通过遍历数组一次来计算前缀和。计算好前缀和数组后，可以在常数时间内查询任意区间的和。
前缀和的优势：

  1. 普通的区间求和
    在没有前缀和技巧时，如果你想求解数组 arr 中一个区间 [l, r] 的和，通常需要通过遍历区间内的元素进行求和。比如，假设我们有一个数组 arr，如果你有多个区间查询（比如查询多个区间的和），那么每次求和都需要遍历一次区间，时间复杂度是
    𝑂(𝑟−𝑙+1)，如果多次查询的话，总时间复杂度会变得很高。
  2. 前缀和优化
    前缀和通过预处理一个额外的数组 prefix_sum 来将多次区间求和的复杂度减少到常数时间。prefix_sum[i] 存储的是 arr[0] 到 arr[i-1] 的和。这样，你只需要一次遍历来计算前缀和数组，然后在进行区间查询时，直接通过前缀和数组来获取结果。这种方式的好处是：
    a. 预处理：计算前缀和数组的时间复杂度是O(n)，仅需遍历一次数组。
    b. 查询：一旦前缀和数组建立起来，任意区间的和查询可以在常数时间 O(1) 内完成。
    时间复杂度对比：
    传统方法：每次区间求和的时间复杂度是 O(r−l+1)，对于多个查询，假设有 q 个查询，最坏情况下时间复杂度是 O(q×n)。
    前缀和：前缀和数组的计算时间是 O(n)，每个区间查询的时间复杂度是 O(1)，因此总时间复杂度是 O(n+q)。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    //示例代码
    #include <iostream>
    #include <vector>

    using namespace std;

    int main() {
        // 输入数据
        vector<int> arr = {1, 2, 3, 4, 5};  // 数组
        int n = arr.size();
        
        // 前缀和数组
        vector<int> prefix_sum(n + 1, 0);  // 初始化前缀和数组，prefix_sum[0] = 0
        
        // 计算前缀和
        for (int i = 0; i < n; i++) {
            prefix_sum[i + 1] = prefix_sum[i] + arr[i];
        }

        // 输出前缀和数组
        for (int i = 0; i <= n; i++) {
            cout << prefix_sum[i] << " ";
        }
        cout << endl;

        // 查询区间和 [l, r]
        int l = 1, r = 3;  // 查询区间 [1, 3] 的和
        int sum = prefix_sum[r + 1] - prefix_sum[l];
        cout << "区间 [1, 3] 的和是: " << sum << endl;

        return 0;
    }

差分

差分数组是一种高效地进行区间更新的技巧。通过维护一个差分数组，在区间 [l, r] 上加上一个常数值，可以在常数时间内完成更新。
差分数组的定义：
假设我们有一个数组 arr，我们可以通过差分数组 diff 来进行快速的区间更新。定义：diff[i]=arr[i]−arri−1
这样，差分数组 diff 的累加就是原始数组 arr。
差分数组更新：
如果我们想在区间 [l, r] 上加上一个常数值 x，我们只需要进行以下两步：
将 diff[l] 加上 x。
将 diff[r + 1] 减去 x（假设 r + 1 在数组范围内）。
最后，通过对差分数组 diff 进行累加，就可以恢复出原始数组 arr。
时间复杂度对比：
传统方法：每次区间更新的时间复杂度是 O(r−l+1)，对于q次更新，最坏情况下时间复杂度是 O(q×n)。
差分数组：每次区间更新的时间复杂度是
O(1)，而恢复数组的时间复杂度是 O(n)。因此总时间复杂度是 O(n+q)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//示例代码
#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 输入数据
    vector<int> arr = {1, 2, 3, 4, 5};  // 原始数组
    int n = arr.size();
    
    // 创建差分数组，初始化为0
    vector<int> diff(n + 1, 0);
    
    // 区间更新：[1, 3] 区间加上 2
    int l = 1, r = 3, x = 2;
    diff[l] += x;
    if (r + 1 < n) {
        diff[r + 1] -= x;
    }

    // 通过差分数组恢复原数组
    vector<int> new_arr(n);
    new_arr[0] = arr[0] + diff[0];
    for (int i = 1; i < n; i++) {
        new_arr[i] = new_arr[i - 1] + diff[i];
    }

    // 输出更新后的数组
    for (int i = 0; i < n; i++) {
        cout << new_arr[i] << " ";
    }
    cout << endl;

    return 0;
}