DP35 【模板】二维前缀和
DP35 【模板】二维前缀和
给你一个 n 行 m 列的矩阵 A ，下标从 1 开始，接下来有 q 次查询，每次查询输入 4 个参数 x1 , y1 , x2 , y2。
请输出以 (x1, y1) 为左上角，(x2,y2) 为右下角的子矩阵的和。
输入描述：
第一行包含三个整数 n，m，q。
接下来 n 行，每行 m 个整数，代表矩阵的元素
接下来 q 行，每行 4 个整数 x1，y1，x2，y2，分别代表这次查询的参数。
输出描述：
输出 q 行，每行代表一次查询的结果。
示例1：
输入：3 4 31 2 3 43 2 1 01 5 7 81 1 2 21 1 3 31 2 3 4
输出：82532
解题思路
一开始我有一个思路，虽然时间复杂度不是很好，其实就是借用了一维前缀和的思路，先开辟一个二维数组 prefix，然后将二维数组的每一行都进行一维前缀和，接着在多次查询中就需要遍历多列去获取每行的前缀和，累加起来，得到最后的前缀和！
虽然这种做法是可以的，但其实时间复杂度没有达到最优处理！所以我们要利用二维前缀和的思想，其实就是一个简单的二维动态规划问题！
那么我们就得想办法看看建立起一个状态转移方程，如下图所示，红色区域是我们要求的元素：
此时如果我们直接从 [x1, y1] 开始求的话，那是比较麻烦的，和我们上面那个思路是差不多的，所以我们不妨这样子想：我们要求的区间，其实可以将其从 [1, 1] 到 [x2, y2] 区间分为下面四个区域：
那我们想，能不能就求