累積和 - 西尾泰和の外部脳

累積和

数列の連続部分列の総和を取りたい

素朴に取ると部分列の長さのオーダー

事前に先頭からの話を取っておくことでO(1)で求められる

準備にO(N)かかる

N回くらい繰り返す時に使うと得

code:python

from itertools import accumulate, chain

acc = list(chain(0, accumulate(XS)))

assert acc4 - acc3 == XS3

assert acc4 - acc1 == sum(XS1:4)

番兵付きの初期化に関しては前者の方が一応有意に速いけど、初期化の頻度を考えると重要な差ではない

code:python

In []: 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などの最中に累積和の動的生成することがある