!累積和を実装するとき、いつもインデックスの扱いに悩んでしまいます。イディオムとしてまとめようと思いました。0-indexの配列、\(a_i\)があるとします。$$目的は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\)とします。\(\mathit{acc}_0\)は0です。$$作成された累積和テーブルは以下のようになります。$$ここで添字がずれるのが混乱の元なんですね。式を立てておきましょう。半開区間とすること(\(s_{[i,i)}\)は空集合なので0)i、jは配列\(a_i\)のものをそのまま使うとなります。結果は以下のようになります。$$\(a_0\)を0とおけば-0indexの場合と同様に扱うことができそうです。$$累積和テーブルは一つずれますが、0-indexと同じ考え方で扱うことができそうです。累積和テーブルの先頭の2つの要素を0で初期化しておかなければならないので注意が必要です。$$作成された累積和テーブルは以下のようになります。$$\(s_{[i,j)}\)は以下のように算出することができます。2分確保しなければならないことでしょうか。累積和を一つずらすことを考えてみましょう。1分確保すればよいです。$$作成された累積和テーブルは0-indexのときと変わりません。$$これは0-indexのときの累積和と全く同じです。j)}\)を計算するときは、以下とします。$$書き出したことで頭がスッキリしてきました。0-indexのときの悩みはなくなりそうです。1-indexのときはどうしたらいいんでしょうか。経験を積んでから考えたほうがよさそうです。Programming(1...昨年のSIGGRAPH参加後、9月ほどからでしょうか。