前缀和以及差分

一：前缀和

题目：http://liuseroj.picp.io/problem/3205
思想：
求区间和的时候本质是：s[r] - s[l - 1]。
当我求1- 10区间的数的时候，本质 s[10] - s[0]，这里就是为什么从1存数据的原因，属于处理边界的手段。处理任何区间都按照相同的运算方式，不用特殊处理。

注意适用于数组下表比较小的范围，注意和离散化的第一个例题做对比，数据范围10^9就会非常大。

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m; // m代表计算区间和的次数
int a[N], s[N];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]); // cpp数组元素没有赋予初始值的时候，默认是0
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];// 利用空间换时间的原理，提前计算前i个数的和
    while (m--) {
        int l, r;
        scanf("%d%d", &l, &r); // 输入区间
        cout << s[r] - s[l - 1] << endl; // 计算某个区间实际用前缀和相减的方式就能实现。
    }
    return 0;
}

• 数据规模大于等于100万的话，建议使用scanf,否则建议使用cin

二：矩阵的和（二维求矩阵和）

题目网址：http://liuseroj.picp.io/problem/3206
原理和一维的本质相类似，其实本质就是公式

求s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
求二维数组面积差额s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]

#include <iostream>
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N], 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", &a[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] + a[i][j];
    while (q--) {
        int x1, x2, y1, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        cout << s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] << endl; 
    }
    return 0;
}

三：差分

前缀和差分本质：
a[N],b[N]

a[N]是b[N]的前缀和数组，b[N]叫做a[N]的差分数组。本质上a[N]就是s[N]的角色

a[1] = b[1]
a[2] = b[1] + b[2]
a[3] = b[1] + b[2] + b[3]
……
根据上面可以推出来：
b[1] = a[1]
b[2] = a[2] - b[1]
b[3] = a[3] - b[2]

核心：如果多次实现前缀和数组的[l, r]区间的元素 + c，可以借助拆分数组，因为拆分数组只要在a[l] + c，这样前缀和数组数组从l往后的元素都会 + c,因为ai = b1 + b2 .. +bi，这样的话，我还需要通过b[r + 1] - c,实现a[]数组r + 1以及往后的元素 - c的目的。

题目：
https://www.acwing.com/problem/content/799/

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
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]); // 构造b[]数组的时候，直接利用insert函数实现。bn = an - an - 1
    while (m--) {
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c); // 这里体现差分的好处，我对前缀和数组多次区间+c操作的时候，最后只要一个结果，这样只需要动b的两个元素，m越大优势自然越明显
    }
    for (int i = 1; i <= n; i++)
        b[i] += b[i - 1]; // 这里就是把b数组变成s数组。不过这个s数组就是计算多次+c操作
    for (int i = 1; i <= n; i++)
        printf("%d ", b[i]);
    return 0;
}

四：差分矩阵

题目：
http://liuseroj.picp.io/problem/3209

原理：
本质上就是上面二维矩阵和和差分的一个思维拓展。
我计算一个二维矩阵 + c的时候，让b[x1][y1] + c,就是让a[x1][y1]开始右下角的全都加c，我只是要下图中的红色部分，因此我需要
b[x1][y2 +1] -= c，b[x2 + 1][y1] -= c，因为a[x2][y2]右下角的部分每个元素多减了一个c，所以需要b[x2 + 1][y2 + 1] += c

#include <iostream>
using namespace std;
const int N = 1010;
int a[N][N], b[N][N];
int x1, y1, x2, y2;
int m, n, q;
void insert(int x1, int y1, int x2, int y2, int c) {
    b[x1][y1] += c;
    b[x2 + 1][y2 + 1] += c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= 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 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++)
            b[i][j] = b[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1] + b[i][j];
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++)
            cout << b[i][j] << " ";
        cout << endl;
    }
    return 0;
}