数列の連続部分列の総和を取りたい
- 素朴に取ると部分列の長さのオーダー
- 事前に先頭からの話を取っておくことでO(1)で求められる
- 準備にO(N)かかる
- N回くらい繰り返す時に使うと得 python
from 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])
番兵付きの初期化に関しては前者の方が一応有意に速いけど、初期化の頻度を考えると重要な差ではない 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などの最中に累積和の動的生成することがある
1次元のゼータ変換 https://qiita.com/convexineq/items/afc84dfb9ee4ec4a67d5