前缀和差分

2023-12-11 21:56:34

前缀和和差分

用处

差分和前缀和是解决矩阵部分和，与解决对一个连续序列进行操作的简化复杂度操作。

前缀和

一维前缀和

预处理 s[i] = s[i-1] + a[i]
s[i] 统计a[1]..a[i]的和，从1开始
s[i] = a[1] + a[2] + ....a[i]
a[l] + ....a[r] = s[r] - s[l-1]

二维前缀和

预处理
s(i,j) = s(i, j - 1) + s(i - 1,j) - s(x-1, y-1) + a(i,j)

s[i][j]表示第i行j列格子左上部分所有元素的和
以(x1,y1)为左上角、(x2,y2)为右下角的部分所有元素和为 = s[x2,y2] - s[x1-1,y2] - s[x2,y1-1] + s[x1-1,y1-1]

差分

一维差分

设 a 是 b的前缀和，即 a[i]表示 b中前 i 个数的和，称 b 是 a 的差分数组
有以下关系：
如果b[l] += c，那么a[l]..都要加c，即 b[l]影响到了 a[l]后面所有的数，这时我们可以通过O(1)的复杂度完成对一段数的操作，
比如要对a[l~r]中这一段数加上 c，但是上面对a[r+1]的数也产生了影响+c。
那么b[r+1] -= c，抵消对a[r+1]...的变化，即最终是a[l~r]中的数加上 c 。

二维差分

二维差分的构造
a[x][y] = s[x][y] + s[x-1][y-1] - s[x][y-1] - s[x-1][y]

二维差分矩阵模板

AcWing 798. 差分矩阵

#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], b[N][N];

// 在a数组中左上角(x1,y1)和(x2,y2)的矩阵区域内加上c，操作差分矩阵b
// 如果两个端点相同，说明在a中的单个点上插入一个数，最终得到的是初始差分矩阵
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()
{
    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;
        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];

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

    return 0;
}

在a数组中左上角(x1,y1)和(x2,y2)的矩阵区域内加上c，操作差分矩阵b
如果两个端点相同，说明在a中的单个点上插入一个数，最终得到的是初始差分矩阵

码农公寓