题目描述

给定一个大小为 \(n \times n\) 的整数矩阵 (A)，元素下标范围为 \(1 \le i,j \le n\)。接下来输入 4 个整数 \(x_1,y_1,x_2,y_2\)，它们分别表示子矩阵的左上角坐标 \((x_1,y_1)\) 和右下角坐标 \((x_2,y_2)\)。请你计算并输出这个子矩阵（包含边界）内所有元素的和。

提示：可以使用二维前缀和的思想来高效解决该问题。

输入格式

1. 第一行：一个整数 \(n\)（\(1 \le n \le 1000\)）。
2. 接下来 \(n\) 行，每行包含 \(n\) 个整数，表示矩阵的每一行。
3. 最后一行：四个整数 \(x_1, y_1, x_2, y_2\)，表示要查询的子矩阵的左上角与右下角坐标，且满足 \(1 \le x_1 \le x_2 \le n\) 且 \(1 \le y_1 \le y_2 \le n\)。

输出格式

• 输出一个整数，表示 \((x_1,y_1)\) 到 \((x_2,y_2)\) 这个子矩阵的元素之和。

样例

输入：

3
1 2 3
4 5 6
7 8 9
2 2 3 3

输出：

28

样例说明

• 输入矩阵为： $[ \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} ]$

• 查询的子矩阵左上角 \((x_1,y_1) = (2,2)\)、右下角 \((x_2,y_2) = (3,3)\)，其元素包括： [ A[2][2] = 5,; A[2][3] = 6,; A[3][2] = 8,; A[3][3] = 9 ]

• 它们的和为 \(5 + 6 + 8 + 9 = 28\)。

思考与提示

1. 如果直接在查询时对子矩阵进行逐行逐列求和，时间复杂度为 (O(n^2))，对于多个查询可能会较慢。

2. 若先预处理一个 二维前缀和 矩阵 (P)，其中 $ [ P[i][j] = \sum_{x=1}^{i} \sum_{y=1}^{j} A[x][y], ]$ 则可以在 (O(1)) 时间内求出任意子矩阵的元素和： $ [ \text{sumSubmatrix}(x_1,y_1,x_2,y_2) = P[x_2][y_2] - P[x_1 - 1][y_2] - P[x_2][y_1 - 1] + P[x_1 - 1][y_1 - 1]. ]$ （注意处理好 \(x_1-1\) 或 \(y_1-1\) 可能为 0 的边界情况。）

3. 通过这一思路，你可以先构建前缀和矩阵，然后在读入查询 \((x_1,y_1,x_2,y_2)\) 时快速计算答案。