前缀和与差分算法

2020-07-12

这段时间噬月在进行算法的复习和学习！

这篇博客将包括前缀和与差分算法（实际上是公式）。

本篇算法模板来自AcWing的y总。

前缀和与差分是逆运算。

前缀和

设有一个长度为$n$的数组$a_1, a_2, a_3, …, a_n$

前缀和$S_i = a_1 + a_2 + … + a_n$

注：从1开始方便统一算法，因为可能使用到$S_0 = 0$

如何求$Si$
递推公式
作用
可以快速求出一个区间内数的和
例：$[l, r]$区间中的数的和：
若遍历区间，时间复杂度为$O(n)$，而使用前缀和公式可以降到$S_r - S_{l - 1}, O(1)$

代码实现只需要计算如下两个式子：

1 2	S[i] = a[1] + a[2] + ... a[i] a[l] + ... + a[r] = S[r] - S[l - 1]

更神奇一些的应用——求子矩阵的和：

1
2
3

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]

如果你学过离散数学的话，不难发现这里头有容斥原理的思想。听起来逼格很高，其实画个图很容易理解。然而在遭遇这样的题目时有时不容易想到使用前缀和去计算。

注：前缀和的初始化当然也需要遍历数组（不管是一维的还是二维的），然而和直接遍历区间去计算，区别在前缀和的做法把这个过程在初始化的时候完成了，$O(n)$的步骤只需要算一次；而直接暴算的话则是每一次都需要遍历。

这里放一个子矩阵的和题目的题解

#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int s[N][N];

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", &s[i][j]);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

    while (q -- )
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
    }

    return 0;
}

差分

设有数组a，构造数组b使得a是b的前缀和数组，则b成为a的差分数组。

如何构造差分数组：

根据前缀和数列的定义，若想使前缀和数列a的区间$[l, r]$之间的元素都加上常数$C$，只需要使差分数列的$b_l + C$且$b_{r + 1} - C$，前者使包括该下标之后的元素都加上$C$，后者使包括该下标之后的元素都减去$C$作为补偿。

于是我们可以先把a数组每个元素看作0，并把初始化的a的过程看作一个个的，在长度为1的区间内加上常数$C$的过程。我们只需要根据上述规则，以数组a的元素值为参数，逆向更改数组b（即处理$b_l + C$和$b_{r + 1} - C$，其中r = l = 第i位），就可以依次得到每一个$b_i$。

放一个差分题

#include <iostream>

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()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

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

    while (m -- )
    {
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    }

    for (int i = 1; i <= n; i ++ ) b[i] += b[i - 1];

    for (int i = 1; i <= n; i ++ ) printf("%d ", b[i]);

    return 0;
}

差分矩阵的情况（即二维的差分）：

当我们把差分矩阵的一个元素$b_{x, y}$加上常数$C$的时候，对应位置的前缀和矩阵的$a_{x, y}$以右下（当然也包括边界的行列）全部会加上常数$C$。

现在假定我们要将子矩阵$b_{x_1, y_1}$（左上）到$b_{x_2, y_2}$（右下）的元素加上一个常数$C$，则可以这样操作：

1	S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

放一个差分矩阵的题

#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[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;
}