子矩阵求和

课程自编 · 二维前缀和

题目描述

给出一个 $n$ 行 $m$ 列的整数矩阵 $a$。有 $q$ 次询问，每次给出左上角 $(x_1,y_1)$ 和右下角 $(x_2,y_2)$，求这个子矩阵中所有元素的和。

输入格式

第一行三个整数 $n,m,q$。接下来 $n$ 行，每行 $m$ 个整数。接下来 $q$ 行，每行四个整数 $x_1,y_1,x_2,y_2$。

输出格式

对每个询问输出一行，表示对应子矩阵的元素和。

数据范围与约定

$1 \le n,m \le 1000$，$1 \le q \le 2\times 10^5$，$|a_{i,j}| \le 10^6$，$1 \le x_1 \le x_2 \le n$，$1 \le y_1 \le y_2 \le m$。

样例输入

3 4 3
1 2 3 4
5 6 7 8
9 10 11 12
1 1 2 2
2 3 3 4
1 1 3 4

样例输出

14
38
78

样例说明

第一个子矩阵为左上角 $2\times2$，和为 $1+2+5+6=14$；第二个为第 $2$ 行第 $3$ 列到第 $3$ 行第 $4$ 列，和为 $7+8+11+12=38$；整个矩阵的和为 $78$。

说明

课程自编题，数据由 src/gen.py 生成。