【備忘録】二次元累積和

あくまで備忘録なんで雑に記録します

まずAリストと、Sリスト初期化

Sリストの個数はN＋１（Sリストの０行と０列は、全部０）

A = [[1, 7, 0, 6], [5, 8, 1, 11], [10, 4, 2, 201], [3, 16, 0, 1]]#4*4リスト
S = [[0]*5 for i in range(5)]#累積リストは+1の、5*5リストでの初期化

N × N 回まわす
Aは0〜N
Sは１〜N+1

for i in range(4):
    for j in range(4):
        S[i + 1][j + 1] += S[i + 1][j] + S[i][j + 1] - S[i][j] + A[i][j]

一次元累積和の書き方の復習①A[1]〜A[2]を②[A[1],A[3])と書いて、③S[3]-S[1]

ところが２次元なので、

赤部分　ー　橙部分　ー　橙部分　だと引きすぎ（青部分）なので、

赤　ー　橙　ー　橙　＋　青

３８　ー　８　ー　１６　＋　１　＝　１５

ans = S[3][3] - S[3][1] - S[1][3]  + S[1][1]
print(ans)#15