コンテンツにスキップ

累積和・いもす法のリンク集

累積和といもす法について、参考になる記事や資料をまとめました。

累積和は、数列 a0,…,aN−1a_0, \dots, a_{N-1} に対して S0=0S_0 = 0、Si+1=Si+aiS_{i+1} = S_i + a_i を前計算しておき、区間 [l,r)[l, r) の和を Sr−SlS_r - S_l で O(1)O(1) で求める手法です。2 次元に広げると、長方形の範囲の和も 4 つの値の足し引きで求められます。

いもす法は、その逆の操作です。「区間 [l,r)[l, r) に xx を足す」を ll に +x+x、rr に −x-x と記録するだけで済ませ、最後に累積和をとって全体の値を一度に求めます。2 次元(長方形への加算)や、木の上(部分木への加算)にも使えます。

資料によって、区間を半開区間 [l,r)[l, r) で書くものと閉区間 [l,r][l, r] で書くものがあります。読み比べるときは、どちらの流儀かに気をつけてください。

  • 累積和を何も考えずに書けるようにする!(けんちょん、Qiita)
    • 半開区間と S0=0S_0 = 0 の流儀で 1 次元の累積和を丁寧に説明し、2 次元の累積和まで扱っています。例題 5 問の C++ の解答つきで、最後にいもす法やしゃくとり法などの発展の話題も紹介しています。
    • 2-1 節の検算で「s13=a1+⋯+a12s_{13} = a_1 + \dots + a_{12}」のように添字が 1 ずれています(定義どおりなら a0a_0 からの和です)。差をとった結果は正しいです。
  • 区間の和を求めるアルゴリズム(区間の更新なし)(アルゴリズムロジック)
    • 1 次元の累積和を、図を多く使って初心者向けに説明しています。C++ の実装と練習問題つきです。
  • 二次元での区間和を求めるアルゴリズム(区間の更新なし)(アルゴリズムロジック)
    • 2 次元の累積和の作り方と長方形の和の求め方を、たくさんの図で説明しています。
    • 最後の「更新がある場合」で 2 次元 BIT の計算量を O(log⁡HW)O(\log HW) としていますが、正しくは O(log⁡Hlog⁡W)O(\log H \log W) です。

コードは int で書かれているものが多いので、和が大きくなる問題では long long を使ってください。

  • いもす法(いもす研)
    • 考案者のいもすさんによる解説です。1 次元の基本から、2 次元、三角形・六角形の座標系、高次(2 次関数など)まで、図を多く使って説明しています。コードは C/C++ で、区間は半開区間です。英語版もあります。
    • 区間の右端 EiE_i が TT になり得るのに、配列を大きさ TT で扱っています。書き写すときは、配列を 1 つ大きく取ってください。
    • 2 次元の説明で、(Ai,Di)(A_i, D_i) を「右上」、(Bi,Ci)(B_i, C_i) を「左下」と呼んでいますが、コードの座標の向きでは逆です。どちらも −1-1 を足す点なので、結果は変わりません。
  • Pythonで累積和・累積積(itertools.accumulate)(note.nkmk.me)
    • itertools.accumulate の使い方の解説です。initial=0 を指定すると先頭に 00 がついた長さ N+1N + 1 の累積和になること、max や operator.mul を渡して累積 max や累積積を作れることが分かります。

木の上のいもす法を一般的に解説した定番の記事は見つからなかったので、問題の解説記事を挙げます。

  • AtCoder ABC 138 D - Ki(けんちょんの競プロ精進記録)
    • 部分木全体への加算を、根の頂点に記録しておき、最後に根から子へ値を配ることで O(N+Q)O(N + Q) にする方法です。配列のいもす法から順に木へ移していく流れで説明しています。コードは C++ の再帰 DFS です。
  • AtCoder ABC 187 E - Through Path(けんちょんの競プロ精進記録)
    • 「部分木の外への加算」を「全体に足して、部分木から引く」に言い換えて、上と同じ方法に帰着させています。
  • いもす法のカテゴリ(けんちょんの競プロ精進記録)
    • いもす法を使う問題の解説がまとまっていて、問題集としても使えます。

累積和・いもす法そのものを解説した講座はありません。

  • 転置原理入門
    • 転置原理の講座で、具体例として区間和クエリ(累積和)の解法を転置すると、区間加算クエリの解法が得られることを示しています。5.4 節で、それが imos 法であると紹介しています。累積和といもす法の関係を知りたい人向けの発展的な読み物で、累積和は前提知識として扱われています。
  • 累積和(日本語版 Wikipedia)、Prefix sum(英語版 Wikipedia)
    • 定義と、inclusive scan・exclusive scan の違い、並列計算での求め方が中心です。区間和を求める使い方の説明はほとんどないので、用語を確かめる程度に使ってください。いもす法(差分配列)の記事は日本語版・英語版ともにありません。
  • Summed-area table(英語版 Wikipedia)
    • 2 次元の累積和の記事で、画像処理(integral image)の文脈で書かれています。dd 次元への一般化の式も載っています。dd 次元の段落では、2 次元の段落と点の名前の付け方が入れ替わっています。
  • Introduction to Prefix Sums(USACO Guide)
    • 1 次元の累積和の入門で、C++・Java・Python のコードと練習問題の一覧があります。
    • 最初の Python のコードは psums[-1] を psum[-1] と書き間違えていて、そのままでは動きません。
  • More on Prefix Sums(USACO Guide)
    • 最大部分配列和、2 次元の累積和(構築の様子が見られる図つき)、差分配列(いもす法)を扱っています。区間は閉区間で書かれています。
  • An Introduction To Difference Arrays(arujbansal、Codeforces)
    • 1 次元の差分配列の短い入門です。閉区間 [L,R][L, R] で書いていて、配列を N+2N + 2 の大きさで取る理由も説明しています。