Idiom: Cumulative Summation Summary
累積和を実装するとき、いつもインデックスの扱いに悩んでしまいます。これが結構時間を喰うので 、しっかりイディオムとしてまとめようと思いました。
例えば0-indexの配列、\(a_i\)があるとします。
$$ \begin{array}{c|ccccc} i & 0 & 1 & 2 & 3 & 4 & 5\\\hline a_i & 1 & 2 & 3 & -4 & -2 & 1 \end{array} $$
目的はO(1)で\(s_{[i,j)}\)を求めることです(準備にはO(N)かかります)。例えば、\(s_{[0,1)}\)は1、\(s_{[0,3)}\)は6、\(s_{[1,3)}\)は5といった具合です。
これを行うには累積和をテーブルとして用意するのが常套手段です。これを\(\mathit{acc}_i\)とします。\(\mathit{acc}_{i+1} = a_i + \mathit{acc}_i\)とします。また、\(\mathit{acc}_0\)は0です。つまり、
$$ \begin{cases} \mathit{acc}_0 = 0\\ \mathit{acc}_{i+1} = a_i + \mathit{acc}_i\ \text{where}\ 0 \leq i < \mathit{size}\\ \end{cases} $$
作成された累積和テーブルは以下のようになります。
$$ \begin{array}{c|cccccc} i & 0 & 1 & 2 & 3 & 4 & 5 & 6\\\hline \mathit{acc}_i & 0 & 1 & 3 & 6 & 2 & 0 & 1 \end{array} $$
ここで添字がずれるのが混乱の元なんですね。しっかり式を立てておきましょう。
$$ s_{[i, j)} = \mathit{acc}_j - \mathit{acc}_i $$
ポイントは、
となります。結果は以下のようになります。
$$ \begin{array}{c|c} s_{[0,1)} = \mathit{acc}_1 - \mathit{acc}_0 = 1 - 0 = 1\\ s_{[0,3)} = \mathit{acc}_3 - \mathit{acc}_0 = 6 - 0 = 6\\ s_{[1,3)} = \mathit{acc}_3 - \mathit{acc}_1 = 6 - 1 = 5\\ \end{array} $$
さて、1-indexの配列の場合にはどうしたらよいでしょう?
$$ \begin{array}{c|ccccc} i & 1 & 2 & 3 & 4 & 5 & 6\\\hline a_i & 1 & 2 & 3 & -4 & -2 & 1 \end{array} $$
\(a_0\)を0とおけば-0indexの場合と同様に扱うことができそうです。
$$ \begin{array}{c|ccccc} i & 0 & 1 & 2 & 3 & 4 & 5 & 6\\\hline a_i & 0 & 1 & 2 & 3 & -4 & -2 & 1 \end{array} $$
累積和テーブルは一つずれますが、0-indexと同じ考え方で扱うことができそうです。累積和テーブルの先頭の2つの要素を0で初期化しておかなければならないので注意が必要です。
$$ \begin{cases} \mathit{acc}_0 = 0\\ \mathit{acc}_1 = 0\\ \mathit{acc}_{i+1} = a_i + \mathit{acc}_i\ \text{where}\ 1 \leq i \leq \mathit{size}\\ \end{cases} $$
作成された累積和テーブルは以下のようになります。
$$ \begin{array}{c|cccccc} i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\\hline \mathit{acc}_i & 0 & 0 & 1 & 3 & 6 & 2 & 0 & 1 \end{array} $$
\(s_{[i,j)}\)は以下のように算出することができます。
$$ s_{[i, j)} = \mathit{acc}_j - \mathit{acc}_i $$
もう一つ気になることといえば、配列は要素数 + 1、また累積和は要素数 + 2分確保しなければならないことでしょうか。
では累積和を一つずらすことを考えてみましょう。この場合の累積和は要素数 + 1分確保すればよいです。
$$ \begin{cases} \mathit{acc}_0 = 0\\ \mathit{acc}_{i} = a_i + \mathit{acc}_{i-1}\ \text{where}\ 1 \leq i \leq \mathit{size}\\ \end{cases} $$
作成された累積和テーブルは0-indexのときと変わりません。
$$ \begin{array}{c|cccccc} i & 0 & 1 & 2 & 3 & 4 & 5 & 6\\\hline \mathit{acc}_i & 0 & 1 & 3 & 6 & 2 & 0 & 1 \end{array} $$
これは0-indexのときの累積和と全く同じです。\(s_{[i, j)}\)を計算するときは、以下とします。
$$ s_{[i,j)} = \mathit{acc}_{j-1} - \mathit{acc}_{i-1} $$
書き出したことで頭がスッキリしてきました。特に、0-indexのときの悩みはなくなりそうです。1-indexのときはどうしたらいいんでしょうか。もう少し経験を積んでから考えたほうがよさそうです。
