問題説明

あなたはm x nの農場を管理しています。各セルにはその区域の収穫量が記録されています。複数のクエリが与えられ、各クエリは矩形領域(r1, c1)から(r2, c2)までの総収穫量を問います。2D累積和を使って各クエリをO(1)で処理してください。

入力

出力

制約条件

• •1 <= m, n <= 1000
• •0 <= 各収穫量 <= 100
• •0 <= r1 <= r2 < m, 0 <= c1 <= c2 < n

例

grid = [[1,2,3],[4,5,6],[7,8,9]], query = (0,0,1,1)

12

grid = [[1,2,3],[4,5,6],[7,8,9]], query = (1,1,2,2)

28