题目描述
输入一个n行m列的整数矩阵,再输入q个询问,每个询问包含四个整数x1, y1, x2, y2,表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数n,m,q。
接下来n行,每行包含m个整数,表示整数矩阵。
接下来q行,每行包含四个整数x1, y1, x2, y2,表示一组询问。
输出格式
共q行,每行输出一个询问的结果。
数据范围
1≤n,m≤1000,
1≤q≤200000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤矩阵内元素的值≤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
观众老爷们,如果本思路对您有帮助,求关注一波~~~
思路
矩阵前缀和和一维前缀和大同小异。其定义是:矩阵前缀和是以其为右下角的矩阵的元素和。
通过矩阵前缀和,我们可以用遍历矩阵的方式来预处理。最后也能很快地处理出矩阵的“区间和”。
首先要会求一个矩阵每个元素(i, j)的左上方的元素之和;
比如 :
i/j 1 2 3
1 3 7 1 3 10 11
2 2 4 0 --> 5 16 17
3 9 4 2 14 29 32
得到此矩阵s
递推公式 s[i][j] = s[i-1][j] + s[i][j-1]-s[i-1][j-1]+matrix[i][j];
其中s[i-1][j-1]是s[i-1][j]和s[i][j-1]重叠计算的区域
那么求左上角为 (row1, col1)到右下角为 (row2, col2)的和:
s[row2][col2]-s[row1-1][col2]-s[row2][col1-1]+s[row1-1][col1-1];
其中s[row1-1][col1-1]是-s[row1-1][col2]和s[row2][col1-1]重叠计算的区域
比如求s(3, 3, 2, 2)
等于黄色的部分总和 - 两个橙色总和 + 红色部分 ( 因为我们发现当我们减去橙色部分, 红色部分多删除一次)
java
import java.util.Scanner;
public class Main{
static int n, m, q;
static int N = 1010;
static int[][] a = new int[N][N], s = new int[N][N];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
q = sc.nextInt();
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
a[i][j] = sc.nextInt();
}
}
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 -- != 0){
int x1, y1, x2, y2;
x1 = sc.nextInt();
y1 = sc.nextInt();
x2 = sc.nextInt();
y2 = sc.nextInt();
System.out.println(s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
}
}
}
python
a = [[0] * 1010 for i in range(1010)]
s = [[0] * 1010 for i in range(1010)]
def main():
global a
global s
n, m, q = list(map(int, input().split()))
for i in range(n):
rows = list(map(int, input().split()))
for j in range(m):
a[i][j] = rows[j]
for i in range(n):
for j in range(m):
s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + a[i][j]
while(q != 0):
x1, y1, x2, y2 = list(map(int, input().split()))
print(s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1])
q -= 1
main()
c++
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N], s[N][N];
int main(){
cin >> 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, y1, x2, y2;
cin >> 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;
}
666,我写python版的还傻傻的把求和后的数组外面加了一圈零,快被蠢哭了,应该先开足数组的┭┮﹏┭┮