累積和

累積和

数列の部分和、およびその和を扱うデータ構造を指す。

累積和を利用すると、区間に対するクエリを \(\mathcal{O}(1)\) で処理できることがある。

以下、扱う配列は0-indexedとする。

配列 \(A = a_0, a_1, \ldots, a_{n-1}\) の累積和は、区間 \([0, n)\) の 部分和

\[s_i = \sum_{i=0}^{n-1} a_i\]

を並べた配列 \(S = s_0, s_1, \ldots, s_{n-1}\) として表現される。

実装

Pythonでは、リストやNumpy配列の累積和を求める関数が実装されている。

from itertools import accumulate

A = [3, 5, -1, 6, -5, 4]
S = list(accumulate(A))
print(S)

[3, 8, 7, 13, 8, 12]

import numpy

S = numpy.cumsum(A)
print(S)

[ 3  8  7 13  8 12]

和に限らず、条件

• 結合法則が成り立つ \((a \cdot b) \cdot c = a \cdot (b \cdot c)\)

• 単位元 \(e\) をもつ \(a \cdot e = e \cdot a = a\)

を満たす二項演算であれば累積を定義できる。

累積ORの実装例を示す。

from itertools import accumulate
import operator

A = [0b010, 0b011, 0b010, 0b010, 0b101]
S = list(accumulate(A, operator.or_))
print(['{:03b}'.format(s) for s in S])

['010', '011', '011', '011', '111']

部分和

部分列 \([0, k)\) の和は、累積和の \(k\) 番目の要素そのものである。

部分列 \([k, n)\) の和は、数列の逆順に対して累積和をとることで求められる。

from itertools import accumulate

A = [3, 5, -1, 6, -5, 4]
S = list(accumulate(A[::-1]))[::-1]
print(S)

[12, 9, 4, 5, -1, 4]

一部の演算については、任意の連続区間に対する累積を扱うことができる。

\([l, r)\) で表される区間 \((l < r)\) の部分和は、累積和 \(S\) を用いて次のように表される。

\[\begin{split}\sum_{i=l}^{r-1} a_i = \left\{ \begin{array}{ll} s_r & (l = 0) \\ s_{r-1} - s_{l-1} & (otherwise) \\ \end{array} \right .\end{split}\]

部分和以外でも、\(s_r, s_l\) に対する逆演算 \(s_r \circ s_l\) が定義されていれば部分累積を \(\mathcal{O}(1)\) で求めることができる。乗算やXORが該当する。

from itertools import accumulate

A = [3, 5, -1, 6, -5, 4]
S = list(accumulate(A))
l = 2
r = 4
print(S[r-1] - S[l-1] if l > 0 else S[r-1])

5