3.2.1. 累積和¶

累積和とは¶

区間を扱うデータ構造の1つ。

累積和を使うと、数列の部分和をを求めるクエリを \(\mathcal{O}(1)\) で処理できる。

数列 \(a_n\) の累積和 \(S_i\) を次のように定義する。

\[\begin{split}\begin{eqnarray} S_i &=& \sum_{i=1}^{n} a_i = a_1 + a_2 + \ldots + a_n \\ \end{eqnarray}\end{split}\]

2つの累積和の差を用いて、数列 \(a_n\) の任意の部分和を表現できる。例えば区間 \([3, 5]\) の部分和は次の通り。

\[\begin{split}\begin{eqnarray} S_5 - S_{(3-1)} &=& (a_1 + a_2 + a_3 + a_4 + a_5) - (a_1 + a_2 + a_3) \\ &=& a_3 + a_4 + a_5 \\ \end{eqnarray}\end{split}\]

実装¶

概要¶

配列 \(a_n\) の累積和を求める。

Pythonでは itertools.accumulate や numpy.cumsum で実装されている。

配列は 0-indexed であることに注意。累積和の定義は次の通り。

\begin{eqnarray} S_i &=& \sum_{i=0}^{n-1} a_i = a_0 + a_1 + \ldots + a_{n-1} \\ \end{eqnarray}

区間 \([i, j]\) の区間和は次のように求める。

\[\begin{split}\sum_{i}^j a = \begin{cases} S_j - S_{i-1} && (i > 0) \\ S_j && (i = 0) \end{cases}\end{split}\]

計算量¶

前処理

操作

メソッド

計算量

数列 \(a\) の累積和

accumulate(a)

\(\mathcal{O}(n)\)
クエリ

操作

メソッド

計算量

区間和 \(\sum_i^j a\)

S[j]-S[i-1]

\(\mathcal{O}(1)\)

使用例¶

[1]:

from itertools import accumulate

A = [3, 5, -1, 6, -5, 4]
S = list(accumulate(A))
print(*S)
print("sum of [{}, {}] is {}".format(0, 3, S[3]))
print("sum of [{}, {}] is {}".format(2, 4, S[4] - S[1]))

3 8 7 13 8 12
sum of [0, 3] is 13
sum of [2, 4] is 0

[2]:

import numpy as np

A = np.int64([3, 5, -1, 6, -5, 4])
S = np.cumsum(A)
print(*S)
print("sum of [{}, {}] is {}".format(0, 3, S[3]))
print("sum of [{}, {}] is {}".format(2, 4, S[4] - S[1]))

3 8 7 13 8 12
sum of [0, 3] is 13
sum of [2, 4] is 0