累積和
数列の連続部分列の総和を取りたい
素朴に取ると部分列の長さのオーダー
事前に先頭からの話を取っておくことでO(1)で求められる
準備にO(N)かかる
N回くらい繰り返す時に使うと得
pythonfrom itertools import accumulate, chain
XS = [1, 2, 3, 4, 5]
acc = list(chain([0], accumulate(XS)))
print(acc) # => [0, 1, 3, 6, 10, 15]
assert acc[4] - acc[3] == XS[3]
assert acc[4] - acc[1] == sum(XS[1:4])
番兵付きの初期化に関しては前者の方が一応有意に速いけど、初期化の頻度を考えると重要な差ではない
pythonIn []: XS = range(1000000)
In []: %timeit list(chain([0], accumulate(XS)))
78.5 ms ± 648 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
In []: %timeit [0] + list(accumulate(XS))
89.2 ms ± 1.3 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
DPなどの最中に累積和の動的生成することがある