前缀和与查分（一维前缀和，二维前缀和（子矩阵的和）一维差分、二维差分（差分矩阵））

1. 前缀和

1. 前缀和的定义

百度给的定义就是：前缀和表示一个序列的前n项和，理解为数组的话就是从下标为1到n（定义成数组时就从下标为1开始接收该序列），而差分就是前缀和的逆运算，前缀和与差分数组是对应关系。

前缀和就是指某个序列的前n项和，类似于数列的求n项和。我们前缀和一般都是从a1开始，默认初始值a0的值为0；那么前缀和的公式就是：s(i) = a(1) + a(2) + ……+ a(i);
原数组: a[1], a[2], a[3], a[4], a[5], …, a[n]
前缀和 Si为数组的前 i项和
前缀和: S[i] = a[1] + a[2] + a[3] + … + a[i]
例如：s[0] = 0
s[1] = a[1]
s[2] = a[1] + a[2]

注意: 前缀和的下标一定要从 1开始, 避免进行下标的转换

1.2. 前缀和的意义（好处）

在我们没有学过前缀和之前，比如说给我们一个整数序列，让我们求某个区间内数的和，那么我们需要依次遍历这部分序列，时间复杂度为O（N），但是，如果我们使用前缀和公式的时候，时间复杂度就是O（1）了。

1.3 一维前缀和

题目描述：

输入一个长度为 n 的整数序列。接下来再输入 m 个询问，每个询问输入一对 l,r。对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。

输入格式：

第一行包含两个整数 n 和 m。第二行包含 n 个整数，表示整数数列。接下来 m 行，每行包含两个整数 l 和 r，表示一个询问的区间范围。

输出格式：

共 m 行，每行输出一个询问的结果。

数据范围：

1≤l≤r≤n,
1≤n,m≤100000,
−1000≤数列中元素的值≤1000

输入样例：

5 3
2 1 3 6 4
1 2
1 3
2 4

输出样例：

3
6
10

#include 
using namespace std;

const int N = 100010;

int n, m;//n表示数组元素个数，m表示要查的次数
int a[N],s[N];//数组a表示原数组，数组s表示数组a的前缀和

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; ++i) scanf("%d",&a[i]);//读取数组a的元素
    
    for(int i = 1; i <= n; ++i) s[i] = s[i - 1] + a[i];//前缀和的公式 前缀和初始化
    
    while(m--)
    {
        int l, r;//l,r表示的是要算的区间的前缀和
        scanf("%d%d", &l, &r);//读取区间
        printf("%d\n",s[r] - s[l - 1]);//计算区间前缀和
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

1.4 二维前缀和（子矩阵的和）

我们要求的是蓝色矩阵（i，j）里面元素的和；紫色矩阵表示的是（1,1）到（i，j-1）的和，红色矩阵表示的是（1,1）到（i-1，j-1）的和，绿色矩阵表示的是（1,1）到（i-1，j）的和。

那么，我们就可以推导出我们要求的蓝色矩阵内元素的和：s[i][j] = s[i-1][j] + s[i][j-1] + a[i][j] - a[i-1][j-1]

那么，更一般的，我们就可以求出（x1，y1）到（x2，y2）之间矩阵内部元素的和了。

紫色面积是指 ( 1,1 )左上角到(x1-1,y2)右下角的矩形面积 ，黄色面积是指(1,1)左上角到(x2,y1-1)右下角的矩形面积；

可以推出以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：：s[x2, y2] - s[x1 - 1, y2] - s[x2, y1 - 1] + s[x1 - 1, y1 - 1]

问题：

#include 
using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], s[N][N];//数组a表示矩阵，数组s表示矩阵a的前缀和

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] + a[i][j] - s[i - 1][j - 1];//前缀和基本公式
            
    while(q--)
    {
        int x1, y1, x2, y2;//输入坐标
        scanf("%d%d%d%d",&x1, &y1, &x2, & y2);
        printf("%d\n",s[x2][y2] - s[x1 -1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

2. 差分

2.1 一维差分

前缀和与差分就相当于高数中的求导和积分，他们是互为逆运算的。
差分数组：
首先给定一个原数组a：a[1], a[2], a[3], a[n];
然后我们构造一个数组b ： b[1] ,b[2] , b[3], b[i];
使得 a[i] = b[1] + b[2 ]+ b[3] +, + b[i]
那么，我们就称数组b为数组a的差分数组。（数组a为数组b的前缀和）

构造方法：
b[1] = a[1]
b[2] = a[2] - a[1]
b[3] = a[3] - a[2]
…
b[n] = a[n] - a[n-1]

这样我们把上面的式子左右都相加，就可以得到 a[n] = b[1] + b[2] + … + b[n]，这样我们就构造了数组a的差分数组。公式：b[n] = a[n] - a[n-1]

那么，我么我们知道了怎么计算差分又有什么用呢？

给定区间[l ,r ]，让我们把a数组中的[ l, r]区间中的每一个数都加上c,即 a[l] + c , a[l+1] + c , a[l+2] + c , a[r] + c;
暴力做法是for循环l到r区间，时间复杂度O(n)，如果我们需要对原数组执行m次这样的操作，时间复杂度就会变成O(n*m)。这时候，我们就可以使用差分了，但是具体怎么使用呢？
我们始终要记得，a数组是b数组的前缀和数组，比如对b数组的b[i]的修改，会影响到a数组中从a[i]及往后的每一个数。
首先让差分b数组中的 b[l] + c ,通过前缀和运算，a数组变成 a[l] + c ,a[l+1] + c, a[n] + c;
然后我们打个补丁，b[r+1] - c, 通过前缀和运算，a数组变成 a[r+1] - c,a[r+2] - c,a[n] - c;

b[l] + c，效果使得a数组中 a[l]及以后的数都加上了c(红色部分)，但我们只要求l到r区间加上c, 因此还需要执行 b[r+1] - c,让a数组中a[r+1]及往后的区间再减去c(绿色部分)，这样对于a[r] 以后区间的数相当于没有发生改变。

题目：

//差分 时间复杂度 o(m)
#include
using namespace std;

const int N = 1e5 + 10;

int n, m;
int a[N], b[N];

int main()
{
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);//读取数组a
        b[i] = a[i] - a[i - 1]; //构建差分数组
    }
    
    int l, r, c;
    
    while (m--)
    {
        scanf("%d%d%d", &l, &r, &c);
        //这里面，其实我们不是把[l,r]的数都加上一个c
        //而是把l加上一个c即可，因为我们在后面算数组a[i]时，b[l]加上一个c，a[l]后面的数就都加上了一个c
        b[l] += c;//将序列中[l, r]之间的每个数都加上c
        b[r + 1] -= c;
    }
    
    for (int i = 1; i <= n; i++)
    {
        a[i] = b[i] + a[i - 1];    //前缀和运算
        printf("%d ", a[i]);
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

2.2 二维差分（差分矩阵）

a[][]数组是b[][]数组的前缀和数组，那么b[][]是a[][]的差分数组
原数组： a[i][j]
我们去构造差分数组： b[i][j]
使得a数组中a[i][j]是b数组左上角(1,1)到右下角(i,j)所包围矩形元素的和
已知原数组a中被选中的子矩阵为 以(x1,y1)为左上角，以(x2,y2)为右下角所围成的矩形区域;

切记：a数组是b数组的前缀和数组，对b数组的b[i][j]的修改，会影响到a数组中从a[i][j]及往后的每一个数。

初始化差分数组也可以通过将(x1, y1) - (x1 - y1) 子矩阵加上a[ i ][ j ]来实现
b[x1][y1] + = a[ i ][ j ];
b[x1,][y2+1] - = a[ i ][ j ];
b[x2+1][y1] - = a[ i ][ j ];
b[x2+1][y2+1] + = a[ i ][ j ];

b[x1][ y1 ] +=c ; 对应图1 ,让整个a数组中蓝色矩形面积的元素都加上了c。
b[x1,][y2+1]-=c ; 对应图2 ,让整个a数组中绿色矩形面积的元素再减去c，使其内元素不发生改变。
b[x2+1][y1]- =c ; 对应图3 ,让整个a数组中紫色矩形面积的元素再减去c，使其内元素不发生改变。
b[x2+1][y2+1]+=c; 对应图4,让整个a数组中红色矩形面积的元素再加上c，红色内的相当于被减了两次，再加上一次c，才能使其恢复。

题目：

#include 
using namespace std;

const int N = 1010;

int a[N][N], b[N][N];//数组a为数组b的前缀和数组，数组b为数组a的差分数组

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, q;
    cin >> n >> m >> q;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            cin >> a[i][j];//读入数组a
            
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            insert(i, j, i, j, a[i][j]);//初始化 构建差分数组
            //同理，根据上述矩阵分析，a[i][j]+c <=> b(i,j) 的那些操作。如果矩阵塌缩为点，即在b(i,j)插入了a(i,j)的值
            // 想象a(i,j) + c的运算a(i,j)设为0，c=(a(i,j))即通过insert函数b(i,j)表达了0到a(i,j)的信息转换。这次insert后b(i,j)的前缀和=a(i,j)
            
    while(q--)
    {
        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)
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];//二维前缀和
            
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j) printf("%d ", b[i][j]);
        puts(" ");
    }
            
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48