差分和前缀和互为逆运算，即差分数组的前缀和数组为原数组，前缀和数组的差分数组为原数组。两者都利用了容斥原理，这一点在二维平面（或二维数组）中体现的更加明显。

  • 一维差分

定义：差分就是将数列中的每一项分别与前一项数做差。

例子：
一个序列1 2 5 4 7 3，差分后得到1 1 3 -1 3 -4 -3

性质：
1.差分数组求前缀和可以得到原序列
2.将愿序列区间[L,R]中的元素全部+1，可以转化操作为差分数组L处+1，R+1处-1.
3.按照性质2得到，每次修改原序列一个区间+1，那么每次差分序列修改处增加的和减少的相同。

  • 二维差分

其实二维差分和一维差分一样，就是更新时一维是更新两个点，二维的更新四个点（四个跟x,y相近的点），然后询问某一个点的值都是前缀和。

根据二维前缀和表示的是右上角矩形的和，由于差分只涉及前面相邻的数（有一维可以推出），并且由前面范围的数相加得到这个位置的数。那么类比二维前缀和和一维差分，可以简单推测出二维差分的公式：

a是原矩阵，p是差分矩阵

p[i][j] = a[i][j] + a[i-1][j-1] - a[i][j-1] - a[i-1][j]

那么如何从差分矩阵得到原矩阵呢？

a[i][j] = p[i][j] + p[i-1][j] + p[i][j-1] - p[i-1][j-1]

对(x1,y1)-(x2,y2)的矩阵+1，对差分矩阵进行更新就可以了。
++p[x1][y1];
++p[x2+1][y2+1];
--p[x1][y2+1];
--p[x2+1][y1];
更新的是以（x1,y1)和（x2,y2)为两个对顶角的矩形。

例题：https://ac.nowcoder.com/acm/contest/7501/J

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
typedef long long ll;
using namespace std;
ll mp[1005][1005];
ll chafen[1005][1005];
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        ll n,m,a,b;
        cin >> n >> m >> a >> b;
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=m;j++)
            {
                cin >> mp[i][j];     //输入原数组
            }
        }
        //i和j的大小到n+1,m+1
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=m;j++)
            {
                chafen[i][j] = mp[i][j] + mp[i-1][j-1] - mp[i-1][j] - mp[i][j-1]; //构造差分数组
            }
        }
        /*
         (i,j) - (i+a-1,j+b-1)
         i+a-1 <= n -> i<=n+1-a
         j+b-1 <= m -> j<=m+1-j
         */
        int flag=1;
        for (int i=1;i<=n+1-a;i++)
        {
            for (int j=1;j<=m+1-b;j++)
            {
                ll c=chafen[i][j];
                if(c<0)
                {
                    flag=0;
                    break;
                }
                else //如果当前的差分数组不小于0，那么说明这个点是可以更新的（把i,j -> i+a,j+b范围 都 减掉当前差分数组的值），因为是一个一个遍历的，当前的差分数组的值，其实就是原数组的值
                {
                    chafen[i][j]=0;
                    chafen[i+a][j+b]-=c;
                    chafen[i][j+b]+=c;
                    chafen[i+a][j]+=c;
                }
            }
            if(flag==0) break;
        }

        /*最后看看是否全为0，如果还有不为0的，说明并不能完全转化*/
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=m;j++)
            {
                if(chafen[i][j]!=0)
                {
                    flag=0;
                    break;
                }
            }
            if(flag==0) break;
        }

        if(flag==0) cout << "QAQ" << endl;
        else cout << "^_^" << endl;
    }
    return 0;
}