前缀和和差分

一、一维前缀和的作用　　

大量的区间求和，把原始数组a的区间操作转换为前缀和的两点操作

有一个数组{2,1,3,6,4}，询问三次结果：
1. 数组第1到第2个元素的和是多少？
2. 数组第1到第3个元素的和是多少？
3. 数组第2到第4个元素的和是多少？

num:index:0 1 2 3 4 5 index
num:array: 2 1 3 6 4 a
sum-array 0 2 3 6 12 16 s

low high
1. 数组第1到第2个元素的和是多少？3 s[2]-s[0] = 3
2. 数组第1到第3个元素的和是多少？6 s[3]-s[0] = 6
3. 数组第2到第4个元素的和是多少？10 s[4]-s[1] = 10

s[high]-s[low-1]

[2,1,3,6,4] a数组 大量的区间求和

1. 数组第1到第2个元素的和是多少？ a1+a2=3 暴力枚举的方法
2. 数组第1到第3个元素的和是多少？ 6
3. 数组第2到第4个元素的和是多少？ 10

num:index:0 1 2 3 4 5 index
num:array: 2 1 3 6 4 a
sum-array 0 2 3 6 12 16 s
原始数组 a [2,1,3,6,4] S4=a1+a2+a3+a4
前缀和数组S [2,3,6,12,16] S3= a3+S2=a1+a2+a3

前缀和数组作用？？？？ 大量的区间求和，把原始数组a的区间操作转换为前缀和的两点操作

数组第i到第j个元素的和是多少 S[j]-S[i-1]

1. 数组第1到第2个元素的和是多少？ S[2]-S[1-1] = 3-0=3
2. 数组第1到第3个元素的和是多少？ S[3]-S[0]=6
3. 数组第2到第4个元素的和是多少？ S[4]-S[1]=10

二、一维差分

1. 现在有一个数列a[0 0 0 0 0 0]，现在想对第3个到第5个元素统一进行加2操作
a[0 0 2 2 2 0]
差分数组d就是相邻两个元素的差排列出来的数列
原始数列a[0 0 0 0 0 0]的差分数列是 d[0 0 0 0 0 0]
一维差分的作用：大量的区间统一更新操作改为两点之间的操作

第3个到第5个元素统一进行加2操作就可以用差分数组的两点操作来完成：
(1) 把差分数组的第3个元素加2，然后把第5+1个位置的元素减2：d[0 0 2 0 0 -2]
(2) 求出这个差分数组的前缀和数组就是我们要的答案：[0 0 2 2 2 0]

三、二维前缀和

1. 如果起始单元格从第一个单元格开始
S[i][j] = S[i][j-1] + S[i-1][j] - S[i-1][j-1] + a[i][j];
2. 如果起始单元格不是从第一个单元格开始，起止单元格分别是：(x1,y1),(x2,y2)
S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]

4 5 1
1 2 2 1 3
3 2 2 1 1
1 1 1 1 1
2 1 3 2 1
2 2 3 4
3. 最终可以把二维原始数组中的区域求和操作转换为这个二维数组前缀和数组的某四个点位之间的操作，这个点位操作
的公式是：
S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1]

 1 #include <iostream>
 2 using namespace std;
 3 
 4 const int N = 1010;
 5 int n, m, q;
 6 int a[N][N], S[N][N];
 7 
 8 /*
 9     二维前缀和公式：
10     1. 如果起始单元格从第一个单元格开始
11         S[i][j] = S[i][j-1] + S[i-1][j] - S[i-1][j-1] + a[i][j];
12     2. 如果起始单元格不是从第一个单元格开始，起止单元格分别是：(x1,y1),(x2,y2)
13         S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]
14 
15     示例数据：
16     4 5 1
17     1 2 2 1 3
18     3 2 2 1 1
19     1 1 1 1 1
20     2 1 3 2 1
21     2 2 3 4
22 
23 */
24 int main() {
25     scanf("%d%d%d", &n, &m, &q);
26     for (int i = 1; i <= n; ++i)
27         for (int j = 1; j <= m; ++j)
28             scanf("%d", &a[i][j]);
29 
30     for (int i = 1; i <= n; ++i) {
31         for (int j = 1; j <= m; ++j)
32             S[i][j] = S[i][j - 1] + S[i - 1][j] - S[i - 1][j - 1] + a[i][j]; // 初始化每个单元格的前缀和
33     }
34     
35     // 输出前缀和
36 //    for(int i=1;i<=n;i++){
37 //        for(int j=1;j<=m;j++){
38 //            printf("%d ",S[i][j]);
39 //        }
40 //        printf("\n");
41 //    }
42 
43     while (q--) {
44         int x1, y1, x2, y2;
45         scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
46         printf("%d\n", S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1]);  // 具体计算某个单元格到某个单元格之间的前缀和
47     }
48 
49     return 0;
50 }