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）空間來存儲累積區域和。