前缀和与差分

前缀和

前缀和数组第 i 个元素表示原数组里前 i 个元素的和，注意下标要从 1 开始。（为了处理边界问题）

前缀和的作用：快速的求出来原数组中一段数的和

A 数组第 i 到第 j 这一段的求和公式

$$Sum = S_j - S_{i-1}$$

题目背景:

输入一个长度为 n 的整数序列。

接下来再输入 m 个询问，每个询问输入一对 l,r。

对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
    int n,m;
    cin >> n >> m;
    vector<int> A;
    vector<int> S;
    A.push_back(0);
    S.push_back(0);
    int a;
    for(int i=1;i<=n;i++)
    {
        cin >> a;
        A.push_back(a);
        S.push_back(S.back()+A.back()); //S.back()是前面所有数的和，在加上A的最新数就是S的最新数
    }
    int l,r;
    while(m--)
    {
        cin >> l >> r;
        cout << S[r] - S[l-1] << endl;
    }

    return 0;
}

二维前缀和

用于快速求出某一个子矩阵的和，S_ij表示从(0,0)到(i,j)这个矩阵的元素和。

以$(x_1,y_1),(x_2,y_2)$为两对角线顶点的矩形部分求和公式

$$Sum = S_{(x_2,y_2)} - S_{(x_2,y_1-1)} - S_{(x_1-1,y_2)} + S_{(x_1-1,y_2-1)}$$

为什么这里要-1呢？

• 因为你要算的矩形面积的边界不能被减掉，你只是在减其它部分矩形。

$S_{(i,j)}$怎么求呢？ 在求$S_{(i,j)}$的时候，假设想象为一个第一区间直角坐标系，那它的下面部分的前缀和已经全部求完了，并且它左边的部分也全部求完了。那么现在我们就可以使用它正下方的位置的前缀和加上左边位置的前缀和再加上本身的值，最后由于左下角的矩阵被加了两次所以我们要减一个$S_{(i-1,j-1)}$

差分

实质上是前缀和的逆运算，从已有数组构造出新数组 已有的数组是新数组的前缀和。

比如 A[1] A[2] A[3] 构造出的 B[1]=A[1], B[2] = A[2] - A[1], B[3] = A[3] - A[2]，这样的话 A 数组就是 B 数组的前缀和。

作用是什么呢？ 当需要对 A 数组中的[l,r]上的每一个数都加 C，暴力的话需要 On 复杂度，但是如果使用 B 数组的话我们可以直接把 B[l]+C，然后再把 B[r+1]-C，这样就能在 O1 复杂度下表示出这个操作。

实际上差分的构造不一定会直接给出原数组 A，我们可以直接构造出 B 数组，考虑下面这个思想： 我们假设一开始的时候原数组是全 0，然后原数组的 n 个值可以看成是 n 个插入操作，第 i 个值实际上就是在给原数组做在区间[i,i]上加 A[i]的操作，所以可以直接体现到差分数组 B 中，即 B[i]+C 和 B[i+1] - C. 差分都不怎么需要考虑构造

题目背景:

输入一个长度为 n 的整数序列。

接下来输入 m 个操作，每个操作包含三个整数 l,r,c，表示将序列中 [l,r] 之间的每个数加上 c。

请你输出进行完所有操作后的序列。

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n,m;
    cin >> n >> m;

    vector<int> s;

    s.push_back(0);

    vector<int> a(n+1);

    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        s.push_back(a[i] - a[i-1]);  // 差分  使s是a的差分数组，题目给出的a是s的前缀和数组
    }

    int l,r,c;
    while(m--)
    {
        cin >> l >> r >> c;
        s[l]+= c;
        s[r+1]-= c;
    }

    int sum = s[0];

    for(int i=1;i<=n;i++)
    {
        sum +=s[i];
        cout << sum << " ";
    }

    return 0;
}

二维差分

类比参考二维前缀和的思想.

题目背景:

输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上 c。

请你将进行完所有操作后的矩阵输出。

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n,m,q;
    cin >> n >> m >> q;

    vector<vector<int>> s(n+1,vector<int>(m+1,0)); // 前缀和矩阵
    vector<vector<int>> c(n+2,vector<int>(m+2,0)); // 差分矩阵

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin >> s[i][j];  //读入矩阵
            c[i][j] = s[i][j] - s[i-1][j] - s[i][j-1] + s[i-1][j-1]; // 计算差分矩阵
        }

    int x1,x2,y1,y2,cNum;
    while(q--)
    {
        cin >> x1 >> y1 >> x2 >> y2 >> cNum;
        c[x1][y1] += cNum;
        c[x2+1][y2+1] +=cNum;
        c[x2+1][y1] -=cNum;    // 注意这里坐标不要写错了  对于一个矩阵的操作 对应的差分矩阵有四个地方需要增减
        c[x1][y2+1] -=cNum;
    }

    vector<vector<int>> ans(n+1,vector<int>(m+1,0));

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            ans[i][j] = ans[i-1][j] + ans[i][j-1] - ans [i-1][j-1] + c[i][j];
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}