Pythonでリストの累積和（プレフィックス合計）を求める方法

Pythonのリストは、順序付けられており変更可能なデータのコレクションです。リストは角括弧 [] を使って記述します。リストの要素にはインデックス番号を指定してアクセスでき、負のインデックスを使うと末尾から数えることができます（-1 は最後の要素を表します）。また、開始位置と終了位置を指定することで、範囲を指定したスライシングが可能です。範囲を指定した場合、戻り値として指定した要素を含む新しいリストが返されます。

累積和（プレフィックス合計）とは

累積和（プレフィックス合計）とは、リストの先頭から各位置までの要素を順番に足し合わせた値を並べたリストのことです。例えば [3, 4, 1] の場合、累積和は [3, 7, 8] となります。統計処理やアルゴリズムの最適化など、さまざまな場面で活用される基本的な操作です。

実装例：リスト内包表記 + sum() + スライシング

ここでは、リスト内包表記と組み込み関数 sum()、そしてリストのスライシングを組み合わせて、累積和のリストを作成する方法を紹介します。

# リスト内包表記 + sum() + リストスライシングを使用

# リストの初期化
test_list = [3, 4, 1, 7, 9, 1]

# 元のリストを表示
print("元のリスト : " + str(test_list))

# 累積和のリストを作成
# 各インデックス i に対して、先頭から i+1 番目までの合計を計算
res = [sum(test_list[: i + 1]) for i in range(len(test_list))]

# 結果を表示
print("累積和のリスト : " + str(res))

実行結果

元のリスト : [3, 4, 1, 7, 9, 1]
累積和のリスト : [3, 7, 8, 15, 24, 25]

コードの解説

range(len(test_list)) によってリストの各インデックス i が順に生成され、test_list[: i + 1] で先頭から i+1 番目までの部分リストを取り出します。その部分リストに対して sum() を適用することで、各位置までの累積和が求められます。

なお、この方法はシンプルで分かりやすい反面、各要素ごとに部分リストの合計を再計算するため、計算量は O(n²) になります。大きなリストを扱う場合は、itertools.accumulate() を使うと O(n) で効率的に累積和を求められます。

from itertools import accumulate

res = list(accumulate([3, 4, 1, 7, 9, 1]))
print(res)  # [3, 7, 8, 15, 24, 25]