差分

• 差分就是数组 a 构造一个查分数组 b （一般选择值为0的两个数组），差分数组 b 的相应位置的前缀和代表了数组 a 中每个位置的结果，对于在一个区间里增加或者减小某个数，对于前缀和来说是o1的，所以对于a中某个区间进行同样的操作也是o1，对a矩阵的操作等价于对b矩阵的操作
• 一维：

如果想要在数组a的 l 到 r 区间的每个数增加 c ，我们可以想到的一种办法是线性扫描一遍，复杂度为n级别，是否可以做到复杂度为1呢？

利用差分可以实现，我们需要一个辅助数组b，其实 a 中每个元素均为 b 数组中对应位置的前缀和，采用b【l】 += c，b【r+1】-= c 可以实现数组 a 从 l 到 r 每个元素增加 c ，由于只有两条语句，所以时间复杂度是1的，最后我们需要把b数组的前缀和求出可得数组 a ，具体请看下面的代码（c++实现）

#include <iostream>
#include <vector>

using namespace std;

const int N = 100000+10;

//构造了一个a的差分数组b，因为此时a数组中 a[i] = b[1] + b[2] + ... + b[i]; a数组为b数组的前缀和
vector<int> a(N,0);
vector<int> b(N,0);

int n, m;

//从a数组的 l 到 r区间内插入c，也就是在b数组的 l 处插入c 在 r+1 处 - c,因为a数组是b的前缀和
void insert(int l, int r, int c){
    b[l] += c;
    b[r + 1] -= c;
}

int main(){
    cin >> n >> m;
    for(int i = 1;i <= n;++i) cin >> a[i];
    
    for(int i = 1;i <= n;++i) insert(i, i, a[i]);//相当于从i 到 i 区间每个数增加c ，表现在b 数组上
    
    for(int i = 0;i < m;++i){
        int l, r, c;
        cin >> l >> r >> c;
        insert(l, r, c);//从 l 到 r 区间插入 c ，表现在b上， 但是实质在a上，因为一会要求b 的 前缀和
    }
    
    for(int i = 1;i <= n;++i) a[i] = a[i - 1] + b[i];//a[i] 为 b[i] 的前缀和 ，就是a[i] 从l 到 r 之间每个数增加c的结果
    
    for(int i = 1;i <= n;++i) cout << a[i] << " ";
    
    return 0;
}

•  二维：

#include <iostream>
#include <vector>

using namespace std;

const int N = 1000+10;
//构造a是b的前缀和矩阵，b是a的差分矩阵
vector<vector<int>> a(N,vector<int>(N,0));
vector<vector<int>> b(N,vector<int>(N,0));

int n, m, q;//n 行 m 列
// x1,y1 为左上角下标 x2,y2为右下角下标 , 函数功能为在 x1,y1 and x2,y2 构成的矩阵每个元素加 c 
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(){
    cin >> n >> m >> q;    
    
    for(int i = 1;i <= n;++i)
        for(int j = 1;j <= m;++j)
            cin >> 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]);
            
    for(int i = 0;i < q;++i){
        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){
            a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + b[i][j];//计算b的前缀和赋值给a
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    
   return 0; 
}