文章目录

• 前缀和
• • 引入
  • 一维前缀和
  • • 思路
    • 代码模板
  • 二维前缀和
  • • 代码模板
• 差分
• • 引入
  • 一维差分
  • • 代码模板
  • 二维差分
  • • 代码模板

前缀和

引入

• 解决的问题：求序列/矩阵一段区间内的和。
• 解决问题的方法：使用一个数组专门存放每个数及之前所有数的和，通过该数组对应区间的差值求和。

一维前缀和

思路

前缀和的思路还是比较简单的，序列中每个数都有一个对应数字，记录截止该数为止所有数的和，那么前5个数的和减去前3个数的和，自然就是第4个数到第5个数的和。

由此可以得出要求出

[

l

,

r

]

[l, r]

[l,r] 区间的数的总和，设对应数组为sum，其公式为：

s

u

m

[

r

]

?

s

u

m

[

l

?

1

]

sum[r]-sum[l - 1]

sum[r]?sum[l?1]

代码模板

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e5+5;
int a[N], b[N], l, r;
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) {
        scanf("%d", &a[i]);
        b[i] += a[i] + b[i - 1];
    }
    while(m --) {
        scanf("%d %d", &l, &r);
        printf("%d
", b[r] - b[l - 1]);
    }
    return 0;
}

二维前缀和

一维到二维需要由点延伸到面，一维的前缀和是起点到指定数的所有数的总和，那么二维的前缀和就是起点到该点矩阵内所有数的和。
要求(x, y)点处的前缀和，可将(x, y)处的值，加上(x, y - 1)和(x-1, y)的前缀和，减去其重叠部分(x-1, y-1)的部分。
如下图所示，要求黑色部分的前缀和，将黑色部分顶点的值，也就是(x, y)的值，加上蓝色部分和红色部分，减去其重合的黑色部分即可。

设前缀和对应的数组为sum，矩阵值的数组为a，前缀和公式为：
sum[x][y] = sum[x][y - 1] + sum[x - 1][y] - sum[x - 1][y - 1] + a[x][y];
得到每个数对应的前缀和后，要求(x1, y1) 和 (x2, y2) 围成矩阵的总和，其公式公式为
sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1]);
推导过程文章二维差分部分有详解，在此不多赘述。

代码模板

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

差分

引入

• 概述：差分为前缀和的逆运算。
• 解决的问题：对一个数组的一个区间统一做同一个处理。
• 方法：
  使用改变序列第i个数的大小，则序列从第i个数开始的子序列总和（也就是前缀和）都会随之改变。

有一序列形如：
1 2 3 4 5 6
此时序列的前缀和序列：
1 3 6 10 15 21
现将第四个数4加一，变为5，此时序列：
1 2 3 5 5 6
对应前缀和变化：
1 3 6 11 16 22

可以看出，一个序列的第i个数加上k，则i之后数的所有的前缀和均随之改变k。

那么根据这个性质，我们可以通过输出前缀和的方式，对i之后的区间统一加上k。

一维差分

我们看这样一道题目：

题目描述
输入一个长度为n的整数序列。
接下来输入m个操作，每个操作包含三个整数l,r,c，表示将序列中

[

l

,

r

]

[l, r]

[l,r]之间的每个数加上c。
请你输出进行完所有操作后的序列。
输入格式
第一行包含两个整数n和m.
第二行包含个整数，表示整数序列。
接下来m行，每行包含三个整数l,r,c，表示一个操作。
输出格式
共一行，包含几个整数，表示最终序列。

数据范围

1

≤

n

,

m

≤

100000

1le n, mle 100000

1≤n,m≤100000

1

≤

l

≤

r

≤

n

1le lle rle n

1≤l≤r≤n

?

1000

≤

c

≤

1000

-1000le cle 1000

?1000≤c≤1000

?

1000

≤

整数序列中元素的值

≤

1000

-1000le 整数序列中元素的值le 1000

?1000≤整数序列中元素的值≤1000

---

分析
根据引入部分，我们可以轻松推出要在

[

l

,

r

]

[l, r]

[l,r]之间的每个数加上c，可以用输出前缀和的方法，把l处的元素加上c，即可将l及之后的前缀和均加上c。
但由于只需要处理l到r，而r后的序列无需加c，所以我们通过在r + 1处加上-c，以此抵消序列在l处加c的影响。

图示

---

这个思路的核心思想就是，把给定序列当作一个序列的前缀和，根据该序列求出对应的原序列，对原序列进行变换，变换后对应的前缀和即为目标序列。

按照引入部分的例子，序列
1 2 3 4 5 6
为一个序列的前缀和，则其对应的原序列为：
1 1 1 1 1 1
如若需要进行的变换为将第三个到第五个数字都加一，按照之前的分析，需要把原序列的第三个数字(l)加一，第六个数字(r + 1)减一，即
1 1 2 1 1 0
变换后对应的前缀和为：
1 2 4 5 6 6
即目的序列。

代码模板

#include <iostream>
using namespace std;
int n, m, c, x, y;
const int N = 1e5 + 6;
int a[N], b[N];	//a数组存放给定序列，b数组存放差分。
void insert(int x, int y, int c) {	// 写一个函数专门处理每一次变换
    b[x] += c;				// l处加c
    b[y + 1] -= c;			// r + 1处-c
}

int main() {
    cin>> n >> m;
    for(int i = 1; i <= n; i ++) {
        scanf("%d", &a[i]);
        insert(i, i, a[i]);	// 求原序列过程即对[i, i]加a[i]
    }
    while(m --) {
        scanf("%d%d%d", &x, &y, &c);
        insert(x, y, c);	// 进行变换
    }
    for(int i = 1; i <= n; i ++) {
        b[i] += b[i - 1];	// 对原序列求前缀和并输出
        printf("%d ", b[i]);
    }
    return 0;
}

二维差分

对应的二维题目：
题目描述
输入一个n行m列的整数矩阵，再输入q个操作，每个操作包含五个整数x1,y1,x2,y2,c，其中(x1,y1)和(x2,y2)表示个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上c。
请你将进行完所有操作后的矩阵输出。
输入格式
第一行包含整数n,m,q。
接下来n行，每行包含m个整数，表示整数矩阵。
接下来q行，每行包含5个整数x1,y1,x2,y2,c,表示一个操作。
输出格式
共n行，每行m个整数，表示所有操作进行完毕后的最终矩阵。

数据范围

1

≤

n

,

m

≤

1000

1le n, mle 1000

1≤n,m≤1000

1

≤

q

≤

100000

1le qle 100000

1≤q≤100000

1

≤

x

1

≤

x

2

≤

1000

1le x_1le x_2le 1000

1≤x1?≤x2?≤1000

1

≤

y

1

≤

y

2

≤

1000

1le y_1le y_2le 1000

1≤y1?≤y2?≤1000

?

1000

≤

c

≤

1000

-1000le cle 1000

?1000≤c≤1000

?

1000

≤

矩阵内元素的值

≤

1000

-1000le 矩阵内元素的值le 1000

?1000≤矩阵内元素的值≤1000

---

题目分析
有了前面的一维差分的引入，导入二维差分就比较方便了，一维是线而二维就是面，操作也是一个面积一个面积的变化，故给定的是矩阵。
根据一维差分，我们同样把给定矩阵当作一个矩阵的前缀和，求出原矩阵后，对原矩阵进行操作。此时把二维的前缀和当作从（x, y）点到矩阵右下角的点的所有数的和。
当要对顶点为(x1, y1)和(x2, y2)的子矩阵，也就是下图红色区域加c，由于二维前缀和影响的是顶点到右下角的区域，我们还需要对橙色和蓝色的区域进行-c的抵消操作，最后灰色区域为两区域重合部分，加了一次但减了两次，最后对灰色区域再次加c，即可完成一次变换处理。

图中绿色绿框代表的区域即(x1, y1)，黄色框代表区域为(x2 + 1, y1)，蓝色框代表的区域为(x1, y2 + 1)，灰色区域为(x2 + 1, y2 + 1)。
则目标红色区域的范围为：(x1, y1) - (x2 + 1, y1) - (x1, y2 + 1) + (x2 + 1, y2 + 1)

代码模板

#include <iostream>
using namespace std;
const int N = 1005;
int a[N][N], b[N][N];	//a数组存放给定矩阵，b数组存放差分。
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() {
    int n, m, c, q, x1, x2, y1, y2;
    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]);
            insert(i, j, i, j, a[i][j]);
        }
    while(q --) {
        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] + b[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1] ;
            printf("%d ", b[i][j]);
        }
        puts("");
    }
    return 0;
}

课后练习：
ACwing一维前缀和模板题
ACwing二维前缀和模板题
ACwing寒假每日一题集训4967
ACwing一维差分模板题
ACwing二维差分模板题