2D累積和による長方形領域和計算
元の行列（4×4）
累積和配列（5×5）
長方形領域和 = S(c+1,d+1) - S(a,d+1) - S(c+1,b) + S(a,b)
目標領域 (a,b) to (c,d)
減算する領域
重複分を加算
計算結果
計算例: 領域 (1,1) から (2,3) の和
ステップ1:
S(3,4) = 78 （右下の大きな長方形）
ステップ2:
S(1,4) = 10 を減算 （上の不要領域）
ステップ3:
S(3,1) = 15 を減算 （左の不要領域）
ステップ4:
S(1,1) = 1 を加算 （重複分を戻す）
結果:
78 - 10 - 15 + 1 =
54
時間計算量
累積和構築:
O(N × M)
各クエリ処理:
O(1)
全体:
O(N × M + Q) （Qはクエリ数）