PrefixSumについて聞きなれない方は多いと思いますが、累積ヒストグラムと言えばピンとくるかもしれません。

PrefixSumの最もシンプルな例を見てみましょう。まず前提とする元データが以下のような配列だったとします。

1 2 3 4 5

これのPrefixSumを算出すると以下のようになります。

1 3 6 10 15

Pythonの文脈では、numpyのcumsum関数がPrefixSumの計算をしてくれます。

import numpy as np
a = np.arange(10)
print(np.cumsum(a))

出力は以下の通りです。

[ 0  1  3  6 10 15 21 28 36 45]