差分矩阵的使用方法

差分归纳

更新：由于前缀和操作的是左上角，差分操作的是右下角，所以两者非常相似，只是坐标的位置发生了变化，并没有什么不同
前缀和操作的是左上角，所以第二个点的坐标x2， y2是没有发生变化的，只是换了下位置即可
但是差分操作的是右下角，所以第一个点的坐标是毫无变化的，x1,y1，只是换下位置即可

1. 差分不许不需要构建，就是开始a和b数组都是0
2. a数组中有数字就当是直接在一段区间内加上的数字罢了
3. 差分矩阵中的某一项加了数值，那么a数组后面的每一项都会加上数值，所有具有连续累加的特点

前缀和求解过程

1. 求解过程中需要使用递归求解，找规律
2. 找规律都是用到x - 1, 或者是 y - 1
3. 构建前缀合sn 或者是差分中的an都是一样的规律，
4. 左边 + 上边 - 左上边 + 当前值
5. 画图的时候采用格子画图，表示当前的元素

差分矩阵的构建过程

1. 从x1, y1 – x2, y2 全 + c
2. 此时看的是右下方，注意的是，如果bi,j + c, 那么 只要用到了bi,j 这个点， 所有的a数组都会加上c, 所以需要减掉
3. 减去的是x2,y2的下方，以及右方， 所以坐标是需要拆开用的，那么加上的就是 右下方 x2 + 1, y2 + 1
4. 如果没有得到答案，记得调试下得到的b数组看是不是满足要求

#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]);

    // printf("------\n");      
    // for(int i = 1;i <= n; i ++)
    // {
    //     for(int j = 1;j <= m;j ++)
    //         printf("%d ", a[i][j]);
    //     cout << endl;
    // }
    // printf("------\n");  


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

    // printf("------\n");      
    // for(int i = 1;i <= n; i ++)
    // {
    //     for(int j = 1;j <= m;j ++)
    //         printf("%d ", b[i][j]);
    //     cout << endl;
    // }
    // printf("------\n");  

    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]);
        cout << endl;
    }

    return 0;
}