2.4 实例3
查询范围和

给定二维矩阵，请找到由左上角（row1，col1）和右下角（row2，col2）定义的子矩阵内的元素之和。

如图2-2所示，矩阵（带有加粗边框）由（row1，col1）=（2，1）和（row2，col2）=（4，3）定义，矩阵内的元素之和为8。

2.4.1 利用一维数组求解

第一种思路是利用一维数组来求解。尝试将二维矩阵视为一维数组的 m 行。为了求区域总和，只需逐行累积。

以第一行为例，我们定义一个动态数组dp[ N +1]，初始化为0。

对于第一个元素，dp[1]=3+dp[0]=3，

对于第二个元素，dp[2]=dp[1]+0=3；

对于第三个元素，dp[3]=dp[2]+1=4；

对于第四个元素，dp[4]=dp[3]+4=8；

对于第五个元素，dp[5]=dp[4]+2=10。

这样，就可以快速知道数组中每行从第一列到第 N 列的元素和。

时间复杂度：每次查询需要 O （ m ）时间，构造函数中的预计算需要 O （ mn ）时间。sumRegion查询需要 O （ m ）时间。

空间复杂度： O （ mn ），即该算法使用 O （ mn ）空间存储所有行的累积和。

2.4.2 利用二维数组求解

第二种思路是将一维数组求和的方法推广到二维数组中。在利用一维数组求解的方法中使用了累积和数组。注意到，累积总和是相对于索引0处的原点计算的。扩展为二维情况，可以相对于原点（0，0）预先计算累积区域总和，如图2-3～图2-6所示。

因此，有Sum（ABCD）=Sum（OD）-Sum（OB）-Sum（OC）+Sum（OA），这里主要考查了索引位置的正确使用。

时间复杂度：每个查询需要 O （1）时间，构造函数中的预计算需要 O （ mn ）时间。

空间复杂度： O （ mn ），即该算法使用 O （ mn ）空间来存储累积区域和。