前缀和 定义

定义一个一维 a[i] 数组 则其前缀和为： $$s[i]=s[i-1]+a[i]$$ 定义一个二维数组 a[i][j] 则其前缀和为 $$s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j]$$ 那么最大的矩形前缀和就等于蓝的矩阵加上绿的矩阵，再减去重叠面积，最后加上小方块，即 s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j]

性质及作用

可以快速的查询某一个区间的和 对于二维矩阵可以快速的求解某一个矩阵的面积

例题

输入一个长度为n的整数序列。

接下来再输入m个询问，每个询问输入一对l, r。

对于每个询问，输出原序列中从第l个数到第r个数的和。

输入格式

第一行包含两个整数n和m。

第二行包含n个整数，表示整数数列。

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

输出格式

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

数据范围

1≤l≤r≤n1≤l≤r≤n

输入样例：

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

输出样例：

3 6 10 #include <iostream> const int N = 100000 + 10; using namespace std; int main() { int n, m; cin >> n >> m; int a[n]; for(int i = 0; i < n; i++) scanf("%d",&a[i]); //计算前缀和 int s[n]; s[0] = 0; for(int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i - 1]; while(m--) { int l, r; scanf("%d %d", &l, &r); cout << s[r] - s[l - 1] <<endl; } return 0; }

输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含四个整数x1, y1, x2, y2，表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

输入格式

第一行包含三个整数n，m，q。

接下来n行，每行包含m个整数，表示整数矩阵。

接下来q行，每行包含四个整数x1, y1, x2, y2，表示一组询问。

输出格式

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

数据范围

1≤n,m≤10001≤n,m≤1000

输入样例：

3 4 3 1 7 2 4 3 6 2 8 2 1 2 3 1 1 2 2 2 1 3 4 1 3 3 4

输出样例：

17 27 21 #include <iostream> using namespace std; int main() { int n, m, q; scanf("%d %d %d",&n, &m, &q); int s[n + 1][m + 1]; //得到原始的二维数组 for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j++) scanf("%d",&s[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];//s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j] //查询操作 while(q--) { int x1, y1, x2, y2; scanf("%d %d %d %d", &x1, &y1, &x2, &y2); cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] << endl; } return 0; }