- 運営しているクリエイター
#累積和
Python で書く累積和
競技プログラミングをしているときにパッと出てこなかったので備忘として。
そもそもどういうときに使用するか?
N の長さを持つ配列中のある区間の総和を知りたいとき。
かかるものとしては
・前処理に O(N)]
・記憶容量に O(N)
・クエリ計算時間結果に O(1)
長さ N の配列 A に対して S[ i + 1 ] = S [ i ] + A[ i ] ( i は 0 ~ N の数値)と
競技プログラミングをしているときにパッと出てこなかったので備忘として。
そもそもどういうときに使用するか?
N の長さを持つ配列中のある区間の総和を知りたいとき。
かかるものとしては
・前処理に O(N)]
・記憶容量に O(N)
・クエリ計算時間結果に O(1)
長さ N の配列 A に対して S[ i + 1 ] = S [ i ] + A[ i ] ( i は 0 ~ N の数値)と