累積和・いもす法のリンク集
累積和といもす法について、参考になる記事や資料をまとめました。
累積和は、数列 に対して 、 を前計算しておき、区間 の和を で で求める手法です。2 次元に広げると、長方形の範囲の和も 4 つの値の足し引きで求められます。
いもす法は、その逆の操作です。「区間 に を足す」を に 、 に と記録するだけで済ませ、最後に累積和をとって全体の値を一度に求めます。2 次元(長方形への加算)や、木の上(部分木への加算)にも使えます。
資料によって、区間を半開区間 で書くものと閉区間 で書くものがあります。読み比べるときは、どちらの流儀かに気をつけてください。
まず読むもの
Section titled “まず読むもの”- 累積和を何も考えずに書けるようにする!(けんちょん、Qiita)
- 半開区間と の流儀で 1 次元の累積和を丁寧に説明し、2 次元の累積和まで扱っています。例題 5 問の C++ の解答つきで、最後にいもす法やしゃくとり法などの発展の話題も紹介しています。
- 2-1 節の検算で「」のように添字が 1 ずれています(定義どおりなら からの和です)。差をとった結果は正しいです。
- 区間の和を求めるアルゴリズム(区間の更新なし)(アルゴリズムロジック)
- 1 次元の累積和を、図を多く使って初心者向けに説明しています。C++ の実装と練習問題つきです。
- 二次元での区間和を求めるアルゴリズム(区間の更新なし)(アルゴリズムロジック)
- 2 次元の累積和の作り方と長方形の和の求め方を、たくさんの図で説明しています。
- 最後の「更新がある場合」で 2 次元 BIT の計算量を としていますが、正しくは です。
コードは int で書かれているものが多いので、和が大きくなる問題では long long を使ってください。
- いもす法(いもす研)
- 考案者のいもすさんによる解説です。1 次元の基本から、2 次元、三角形・六角形の座標系、高次(2 次関数など)まで、図を多く使って説明しています。コードは C/C++ で、区間は半開区間です。英語版もあります。
- 区間の右端 が になり得るのに、配列を大きさ で扱っています。書き写すときは、配列を 1 つ大きく取ってください。
- 2 次元の説明で、 を「右上」、 を「左下」と呼んでいますが、コードの座標の向きでは逆です。どちらも を足す点なので、結果は変わりません。
Python
Section titled “Python”- Pythonで累積和・累積積(itertools.accumulate)(note.nkmk.me)
itertools.accumulateの使い方の解説です。initial=0を指定すると先頭に がついた長さ の累積和になること、maxやoperator.mulを渡して累積 max や累積積を作れることが分かります。
木の上のいもす法
Section titled “木の上のいもす法”木の上のいもす法を一般的に解説した定番の記事は見つからなかったので、問題の解説記事を挙げます。
- AtCoder ABC 138 D - Ki(けんちょんの競プロ精進記録)
- 部分木全体への加算を、根の頂点に記録しておき、最後に根から子へ値を配ることで にする方法です。配列のいもす法から順に木へ移していく流れで説明しています。コードは C++ の再帰 DFS です。
- AtCoder ABC 187 E - Through Path(けんちょんの競プロ精進記録)
- 「部分木の外への加算」を「全体に足して、部分木から引く」に言い換えて、上と同じ方法に帰着させています。
- いもす法のカテゴリ(けんちょんの競プロ精進記録)
- いもす法を使う問題の解説がまとまっていて、問題集としても使えます。
AtCoder Algorithm Lectures
Section titled “AtCoder Algorithm Lectures”累積和・いもす法そのものを解説した講座はありません。
- 転置原理入門
- 転置原理の講座で、具体例として区間和クエリ(累積和)の解法を転置すると、区間加算クエリの解法が得られることを示しています。5.4 節で、それが imos 法であると紹介しています。累積和といもす法の関係を知りたい人向けの発展的な読み物で、累積和は前提知識として扱われています。
百科事典・英語の資料
Section titled “百科事典・英語の資料”- 累積和(日本語版 Wikipedia)、Prefix sum(英語版 Wikipedia)
- 定義と、inclusive scan・exclusive scan の違い、並列計算での求め方が中心です。区間和を求める使い方の説明はほとんどないので、用語を確かめる程度に使ってください。いもす法(差分配列)の記事は日本語版・英語版ともにありません。
- Summed-area table(英語版 Wikipedia)
- 2 次元の累積和の記事で、画像処理(integral image)の文脈で書かれています。 次元への一般化の式も載っています。 次元の段落では、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 次元の差分配列の短い入門です。閉区間 で書いていて、配列を の大きさで取る理由も説明しています。
- ABC037 C - 総和:長さ の区間の和を、累積和でそれぞれ で求めます。
- 競プロ典型 90 問 010 - Score Sum Queries(★2):組ごとに累積和を作り、区間和のクエリに答えます。
- ABC122 C - GeT AC:「そこから
ACが始まるか」の の列の累積和をとります。区間の端の扱いに注意が必要です。 - ABC084 D - 2017-like Number:エラトステネスの篩で条件を満たす数を求め、その個数の累積和をとります。
- AGC023 A - Zero-Sum Ranges:和が の区間は、累積和が等しい組と言い換えられます。
- ABC105 D - Candy Distribution:和が の倍数の区間は、累積和を で割った余りが等しい組です。
- ABC134 C - Exception Handling:前からと後ろからの累積 max で、「1 つを除いた最大値」を求めます。
- ABC005 D - おいしいたこ焼きの焼き方:2 次元の累積和で、すべての長方形の和を求めます。
- ABC086 D - Checker:座標を周期 で畳んでから、2 次元の累積和を使います。
- ABC014 C - AtColor:1 次元のいもす法の基本で、区間が最も多く重なる点を求めます。区間は両端を含みます。
- ABC035 C - オセロ:各マスが裏返された回数をいもす法で数え、偶奇で色を決めます。
- ABC183 D - Water Heater:時刻ごとの使用量をいもす法で求めます。
- ABC188 D - Snuke Prime:日付が大きいので、料金が変わる日だけを取り出して(座標圧縮して)いもす法を使います。
- 競技プログラミングの鉄則 A09 - Winter in ALGO Kingdom:2 次元のいもす法の基本です。
- 競プロ典型 90 問 028 - Cluttered Paper(★4):2 次元のいもす法で、各マスに重なっている紙の枚数を求めます。
- ABC138 D - Ki:木の上のいもす法の基本です。上のけんちょんさんの記事が解説です。
- ABC187 E - Through Path:部分木の外への加算も、木の上のいもす法で扱えます。
このブログの記事
Section titled “このブログの記事”- ABC477 C - Range Search Query
- 各位置から が始まるかの の列の累積和で、区間の中に が何回現れるかを数えています。
- ABC477 E - Wheel Distance
- 円環の上の 2 点間の距離を、辺の長さの累積和で求めています。
- ABC478 C - Sort Subarray
- Uiua のコードで、ソート前後でずれている位置の範囲を、前と後ろからの累積和で求めています。
- SamCoding Round 7 (Div. 2) F - Subarrays Divisible by K
- 和が で割り切れる区間を、累積和の余りが等しい組として数えています。
- SamCoding Round 7 (Div. 2) I - Subarrays in Range L-R
- 和が に入る区間を、累積和の値の範囲の条件に言い換えて数えています。
- SamCoding Round 7 (Div. 2) K - Blueprints Washed by the Rain
- DP の遷移を、後ろからの累積和で高速化しています。
- Blitz Round #25 B - Jump Trip Score
- 接頭辞の和の最大値と接尾辞の和の最大値を累積和で求め、境目を全通り試しています。
- Blitz Round #25 C - Root Value
- 区間の積を直接計算する代わりに、素数ごとの指数の累積和を使って区間の積の素因数分解を求めています。
- DOJ Beginner Contest 7 B - tourist vs rainboy
- 各問題を解き終える時刻が累積和になることを使って、ペナルティを計算しています。
- ABC478 D - Range Set Insertion Query
- 値ごとに重なった区間を併合してから、いもす法で数えています。
- ABC479 E - Larger Component
- 「部分木への加算」と「部分木の外への加算」を、木の上のいもす法でまとめて処理しています。