题目描述
对于一个二维矩阵,里面每一个点的值为a[i][j];Sij表示ij左上角所有元素的和,如果要求对于以x1y1为左上角,x2y2为右下角此矩阵所有元素的和,
=S[x2][y2]-S[x1][y1-1]-S[x1-1][y2] +S[x1-1][y1-1];画图看即懂
求Sij:
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + a[i][j]
}
}
思考
思考,对于二维前缀和,求前缀和时候公式为
S[i][j] = S[i][j-1] + S[i-1][j] + re[i][j] - S[i-1][j-1]
求区间和是对[x1]y1到[x2][y2]的和为
S[x2][y2]-S[x1-1][y2]-S[x2][y1-1]+S[x1-1][y1-1]
对于一维,求前缀和为S[i] = S[i-1] + re[i] 或者re[i] += re[i-1]
求区间[a,b] = S[b] - S[a-1]
(二维前缀和) $O(nm)$
对于其复杂度就是预处理时为o(nm),后面求一段区间和就是o(1)了,因此总为o(nm)
参考文献
https://www.acwing.com/video/622/
python 代码
# 1.输入
n,m,q = map(int,input().split())
re = [[0 for i in range(m+1)]]
for i in range(n):
re.append([0] + list(map(int,input().split())))
S = [[0 for j in range(m+1)] for i in range(n+1)]
# 2.得到前缀和
for i in range(1,n+1):
for j in range(1,m+1):
S[i][j] = S[i][j-1] + S[i-1][j] + re[i][j] - S[i-1][j-1]
# 3.求区间和
for i in range(q):
x1,y1,x2,y2 = map(int,input().split())
print(S[x2][y2]-S[x1-1][y2]-S[x2][y1-1]+S[x1-1][y1-1])