第一讲 基础算法 - 05 前缀和和差分

[toc]

AcWing 算法基础课笔记 1.基础算法-CSDN
AcWing《算法基础课》第1章 算法基础 - AcWing
AcWing 795 前缀和 - 糖豆爸爸 - 博客园
AcWing 796. 子矩阵的和 - 糖豆爸爸 - 博客园

---

前缀和和差分

1 一维前缀和

一维前缀和是针对一维数组而言的，它表示数组中从起始位置到当前位置的元素的累积和, 也就是区间和

通过计算前缀和, 可以快速获取数组中任意一个区间 [l, r] 的区间和，即 a[l] + a[l+1] + ... + arr[r], 而不需要每次都重新计算. 这样可以在一些需要频繁计算区间和的情况下大大提高效率, 例如动态规划, 子数组问题等

总结公式:

前缀和: S[i] = a[1] + a[2] + ... a[i]
区间和：S[r] - S[l - 1] = a[l] + ... + a[r]

说明:

1. 假设 S0 = a0 = 0
2. 数组 a 和 S 的第 1 个元素都不存储（下标为 0 ）, 而从第 2 个元素开始存储（下标为 1）
3. 注意遍历范围是 1 ~ n
4. 在一些不涉及 a[i] 的题目中，不必要存储 a[i] 的值，只需要存储 S[i] 就足够

---

一维前缀和应用:
复杂度由 O(n) 降为 O(1)

#include <bits/stdc++.h>
#define endl '\n';
using namespace std;

const int N = 100010;
int n, m;
int a[N], s[N];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m;
    for ( int i = 1; i <= n; i ++ ) cin >> a[i];
    
    for ( int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];     // 预处理前缀和数组
    
    while( m -- ){
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << endl;    // 计算区间和
    }
    
    return 0;
}

2 二维前缀和

二维前缀和是指在二维数组中计算从左上角到右下角任意子矩形区域的元素和。

总结公式:

前缀和: S[i,j] = S[i-1,j] + S[i,j-1] - S[i-1,j-1] + a[i,j]
区间和: S[ab,ij] = S[i,j] - S[a-1,j] - S[i,b-1] + S[a-1,b-1]

说明：

1. 假设数组 a 中行下标或列下标为 0 的项都是 0
2. 读入数组 a 和初始化前缀和数组 S 的过程可以合并在一起
3. 注意遍历范围是 1 ~ n
4. 在一些不涉及 a[i][j] 的题目中，不必要存储 a[i][j] 的值，只需要存储 S[i][j] 就足够

二维前缀和应用:
复杂度由 O(n * m) 降为 O(1)

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 1010;
int n, m, q;
int a[N][N], s[N][N];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m >> q;
    for ( int i = 1; i <= n; i ++ )
        for ( int j = 1; j <= m; j ++ ){
            cin >> a[i][j];
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];    // 预处理前缀和数组
        }
        
    while ( q -- ){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] << endl;      // 求区间和
    }
    
    return 0;
}

3 一维差分

差分数组是一种用于高效处理数组区间修改的技术. 它通过在两个相邻元素之间存储差值来表示原始数组的变化情况.

1. 定义: b[i] = a[i] − a[i−1], 称 b 数组是 a 数组的差分数组.
2. 作用: 在某个区间 [l, r] 的多次操作都加上 (或减去) 一个数 x 时, 一维差分可以大大提高运算速度.
3. 小结:

1. a 数组中, 每个数字后面减前面得到的数字填入b数组, b 数组就叫 a 数组的差分数组.
2. 同时, a 数组就是 b 数组的前缀和数组.
3. 通过 “叠加” 差分数组, 就可以还原出 “原数组” 的每一个数字!
4. 前缀和与差分互为逆运算, 有原数组可以计算出差分数组; 有差分数组, 也可以还原成原数组.

假设原始数组为 a = {1, 2, 3, 4, 5}, 我们要对区间 [2, 4] 进行修改, 将其所有元素增加 2.

1. 初始化差分数组 b = {0, 0, 0, 0, 0}.
2. 进行区间修改, 将 b[2] 增加 2, b[5] 减去 2. 现在 b = {0, 2, 0, 0, -2}.
3. 计算前缀和, 得到最终的结果数组 b = {0, 2, 2, 2, 0}, 这个数组就是原始数组 a 在区间 [1, 5] 的累积和.

---

总结公式:
这里根据 a[ ] 数组, 构造 b[ ] 数组, 使得 a 是 b 的前缀和

// 给区间 [l, r] 中的每个数加上 c
void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

一维差分应用:
复杂度由 O(n) 降为 O(1)

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int n, m;
int a[N], b[N];

void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m;
    for ( int i = 1; i <= n; i ++ ){
        cin >> a[i];
        insert(i, i, a[i]);     // 构造, 预处理差分数组
    }
    
    while ( m -- ){
        int l, r, c;
        cin >> l >> r >> c;
        insert(l, r, c);        // 进行区间修改
    }
    
    for ( int i = 1; i <= n; i ++ ){
        b[i] += b[i - 1];       // 计算一维前缀和
        cout << b[i] << " ";
    }
    cout << endl;
    
    return 0;
}

4 二维差分

给 [x1, y1] 与 [x2, y2] 构成的矩形范围内的每个数加上c

总结公式:

// 给以 (x1, y1) 为左上角, (x2, y2) 为右下角的子矩阵中的所有元素加上c
void insert(int x1, int y1,int x2, int y2, int c)
{
    S[x1, y1] += c;
    S[x2 + 1, y1] -= c;
    S[x1, y2 + 1] -= c;
    S[x2 + 1, y2 + 1] += c;
}

说明:

• insert()函数规律
  • 下标出现 2 的部分都 + 1
  • 范围最大最小的 += c, 其它 -= c
• 注意遍历范围是 1 ~ n

二维差分应用:
复杂度由 O(n * m) 降为 O(1)

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 1010;
int n, m, q;
int a[N][N], b[N][N];

// 功能: 二维差分构建
void insert(int x1, int y1, int x2, int y2, int c){
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m >> q;
    for ( int i = 1; i <= n; i ++ )
        for ( int j = 1; j <= m; j ++ ){
            cin >> a[i][j];
            insert(i, j, i, j, a[i][j]);    // 构造, 预处理差分数组
        }
    
    while ( q -- ){
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);      // 进行区间修改
    }
    
    // 转换成二维前缀和数组
    for ( int i = 1; i <= n; i ++ ){
      for ( int j = 1; j <= m; j ++ )
        {
             b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];    // 二维前缀和公式
             cout << b[i][j] << " ";
        }
        cout << endl;
    }
    
    return 0;
}