累積和解説

背景

配列の特定区間の和を早く求めるためのアルゴリズム。具体的には $O(N)$ で事前に必要な計算をし、特定区間の和は $O(1)$ の計算量で求めることができる。特定区間の和が $O(1)$ で求められるため何度も特定区間の和を求める必要がある場合に有効である。

原理

長さ $N$ の配列を $a=[a_{0}, \dots, a_{N-1}]$ とする。このとき、 $n$ 番目の要素が $s_{n} = s_{n-1} + a_{n-1}$ で(ただし $s_{0} = 0$ とする)長さが $N+1$ の配列 $s=[s_{0}, \dots, s_{N}]$ を事前に作成すれば、区間 $a_{i}$ から $a_{j}$ の和は $s_{j+1} - s_{i}=s[j+1] - s[i]$ で $O(1)$ の計算量で求めることができる。事前に作成する配列 $s$ は以下のように $O(N)$ の計算量で求めることができる。

for i in range(N):
    s[i+1] = s[i] + a[i]

「$s_{n} = s_{n-1} + a_{n}$としても良いのでは？」と思うかもしれないが、そうすると区間 $a_{i}$ から $a_{j}$ の和は

\begin{cases}
s_{j} & (i = 0) \\
s_{j} - s_{i-1} & (i \geq 1)
\end{cases}

となり場合分けが必要になるため、$s_{n} = s_{n-1} + a_{n-1}$ (ただし $s_{0} = 0$)としている。

参考文献

累積和を何も考えずに書けるようにする！ - Qiita https://qiita.com/drken/items/56a6b68edef8fc605821