差分

思想

一维差分
- 一直a1, a2, …, an. 构造b1, b2, …, bn 使得 ai = b1 + b2 + … + bi b数组称为a数组的差分，a成为b的前缀和。
- 一维差分的用处：假设想对a[L~R]中每个数都加上一个常数C. 即 a[L] + C, a[L+1] + C, …, a[R] + C
  1. a[L] + C = b[1] + b[2] + … + b[L] + C
  2. a[L + 1] + C = b[1] + b[2] + … + b[L + 1] + C = b[1] + b[2] + … + b[L] + C + b[L + 1] 注：只需要对b[L] + C 即可对L后的每个a加上一个C
  3. 对 b[R + 1] - C 则 a[R + 1] 后的数依旧保持不变
  4. a[R + 1] = b[1] + b[2] + … + b[L] + C + … + b[R] + b[R + 1] - C 注加C减C互相抵消了
- 初始化一维差分数组
  1. 初始化原数组为a1, a2, …, an 为0, 从原数组i处插入一个数C(可以通过C构造出原数组), 等价于在差分数组 i 处加上一个C, 在 i + 1处减去一个C.
  2. 构造差分数组可以通过 b[i] += C; b[i + 1] -= C 构造。
二维差分
- 原数组为a[i][j], 差分数组为b[i][j]
- 核心操作：给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有前缀和数租a[i][j]加上C,
- 设差分数组为s[i][j], 则对于差分数组(x1, y1), (x2, y2)而言对这中间的a[i][j] + C 等价于
  1. b[x1, y1] += C
  2. b[x1, y2 + 1] -= C
  3. b[x2 + 1, y1] -= C
  4. b[x2 + 1, y2 + 1] += C

特点

一维特点
- b1 = a1; b2 = a2 - a1; b3 = a3 - a2; ….; bn = an - an-1

//一维
#include <iostream>
#include <algorithm>

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()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <=n; i++) insert(i, i, a[i]);  //根据在i, i处插入一个a[i] 来构造差分数组

    while (m--)
    {
        // 对原数组在 l, r 中间加入一个c 等价于在差分数组b[l] + c, b[r + 1] - c
        int l, r, c;
        cin >> l >> r >> c;
        insert(l, r, c);  //构造出新的差分和数组
    }

    //由新的差分新的原数组
    for (int i = 1; i <= n; i++) a[i] = a[i - 1] + b[i];

    //读出
    for (int i = 1; i <= n; i++) printf("%d ", a[i]);
    puts(""); //换行
    return 0;
}

//二维
#include <iostream>
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[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= c;
    b[x2 + 1][y2 + 1] += c;
}


int main()
{
    scanf("%d%d%d", &n, &m, &q);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            insert(i, j, i, j, a[i][j]);

    while (q -- )
    {
        int x1, y1, x2, y2, c;
        scanf("%d%d%d%d%d", &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++)
            a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j];

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            printf("%d ", a[i][j]);
        }
        puts("");
    }


    return 0;
}

差分

思想

特点

FEATURED TAGS