どもども～～ こんにちは。ながたでございます。
先日の ABC 331 D - Tile Pattern を見て、執筆したくなりました。 この記事は、２次元累積和の亜種や実装方針などを網羅的に検討して回った結果、結局「コレ」でよいですよねという感じの記事になっております。深追いしたくない方は結論からピックアップしていただけるとです。ぜひです～～～～👌
アッ！ あとチャンネル登録もぜひです。競技プログラミングの動画、まだ少ないですが今後増えていくと思いますゆえなにとぞです✋
結論
たいていのケースでは「① A. 貰うDPで計算する方法」がおすすめです。
これで困ることはほぼないと思いますが、マスターしたい方はぜひとも全部ご覧頂いて、ええ。
また、コードはコピペで使えるように、import を省略せずに書いていますが、num::Zero トレイトを使用しているため、std オンリーで使いたい場合はそこだけ注意かもです。（AtCoder 環境なら num が使えるので問題なしですが。）
２次元累積和の４つの形
好みや用途で使い分けていただきたいのですが、基本は①でOK。②も可。③・④はおそらくほぼメリットなしです。
↓ これを $A$ として
↓ 累積和 $B$ は東京・千葉に次のような４つのキャンパスがあります。
| サイズ | Prefix sum 前から累積和 |
Suffix sum 後ろから累積和 |
|---|---|---|
| $(H + 1) \times (W + 1)$ （０を追加する方法） |
 |
 |
| $H \times W$ （０を追加しない方法） |
|
|
２次元累積和８つの構築方法
４つのキャンパスそれぞれに２つの構築方法が考えられますが、基本は A で OK です。B も悪くはなしです。
さて詳細を、「① 前から累積和・０を追加する方法」を例に解説いたしましょう。
① A. 貰うDPで計算する方法
- 📈 実装が短いです。
- 📉 引き算が定義できることを要求します。
$(i, j)$ の昇順に確定していく方法です。これでよいのではないでしょうか。お疲れ様でした～～ 解散です。あとはチャンネル登録だけしてブラウザバックしていただいて✋
use num::Zero; use std::ops::{Add, Sub}; fn prefix_sum<T>(h: usize, w: usize, mut f: impl FnMut(usize, usize) -> T) -> Vec<Vec<T>> where T: Zero + Add<Output = T> + Sub<Output = T> + Copy, { let mut sum = vec![vec![T::zero(); w + 1]; h + 1]; for i in 0..h { for j in 0..w { sum[i + 1][j + 1] = f(i, j) + sum[i][j + 1] + sum[i + 1][j] - sum[i][j]; } } sum }
① B. 高速ゼータ変換の易しいやつで計算する方法
- 📈 加算２回、減算０回と演算回数が少ない
- 📉 実装が長い
- 📉 Rust 特有の問題ですが、
AddAssignを使うので所有権が面倒。（Addで書き換えれば一応大丈夫）（ジェネリックにしないで数値型で直接書く場合は問題になりません）
とりあえず $B _ { i + 1, j + 1 } \leftarrow A _ { i, j }$ しておいて、そのあとで $i$ 方向、$j$ 方向それぞれ累積和を取る方法です。わかる方は母関数で理解すると理屈は A より易しいです。
当然ですが計算順が大事ですから、$i$ 方向、$j$ 方向の累積和のループを単純にまとめた実装は誤りなので注意です。で、その差分をなんとか調整しようとすると結局 A と同じ実装にな ってしまうかもです。
ちなみになのですが高速ゼータ変換は本来一般次元の累積和みたいなやつに使うアルゴリズムですから、今回のように次元が非常に低い（２次元）場合には、実行速度はほとんど変わらないのではないかとです。
use num::Zero; use std::ops::AddAssign; fn prefix_sum<T>( h: usize, w: usize, mut f: impl FnMut(usize, usize) -> T, ) -> Vec<Vec<T>> where T: Zero + AddAssign + Copy, { let mut sum = vec![vec![T::zero(); w + 1]; h + 1]; for i in 0..h { for j in 0..w { sum[i + 1][j + 1] = f(i, j); } } for i in 1..=h { for j in 1..=w { let x = sum[i - 1][j]; sum[i][j] += x; } } for i in 1..=h { for j in 1..=w { let x = sum[i][j - 1]; sum[i][j] += x; } } sum }
② A. 貰うDPで計算する方法
実はこれも楽、といますか ① A とほぼ同じ実装です。Suffix sum が欲しい場合はこれがオススメかもです。
ほぼ変わらないのですが、一応 ① と比べたメリット・デメリットです。
- 📈 $A$ と $B$ で添字がずれない
- 📉 ちょっと分かりづらい
- 📉 末尾に追加できない（普通しないと思いますが）
また Suffix 系全般の注意ですが、意外とこの .rev() 忘れがちです。
use num_traits::Zero; use std::ops::{Add, Sub}; fn suffix_sum<T>(h: usize, w: usize, mut f: impl FnMut(usize, usize) -> T) -> Vec<Vec<T>> where T: Zero + Add<Output = T> + Sub<Output = T> + Copy, { let mut sum = vec![vec![T::zero(); w + 1]; h + 1]; for i in (0..h).rev() { for j in (0..w).rev() { sum[i][j] = f(i, j) + sum[i + 1][j] + sum[i][j + 1] - sum[i + 1][j + 1]; } } sum }
② B. 高速ゼータ変換の易しいやつで計算する方法
これも ① B とほぼ同じですが、一応 ① B と比べた ② B のメリット・デメリット（のうち、① と比べた ② のそれにないもの）をばです。
- 📈 ループ範囲が自然に
0..h,0..wになる（出典: 熨斗袋さんのご指摘）
use num_traits::Zero; use std::ops::AddAssign; fn suffix_sum<T>(h: usize, w: usize, mut f: impl FnMut(usize, usize) -> T) -> Vec<Vec<T>> where T: Zero + AddAssign + Copy, { let mut sum = vec![vec![T::zero(); w + 1]; h + 1]; for i in (0..h).rev() { for j in (0..w).rev() { sum[i][j] = f(i, j); } } for i in (0..h).rev() { for j in (0..w).rev() { let x = sum[i + 1][j]; sum[i][j] += x; } } for i in (0..h).rev() { for j in (0..w).rev() { let x = sum[i][j + 1]; sum[i][j] += x; } } sum }
③ A. 貰うDPで計算する方法
先頭の０がないため境界値で場合分けが必要でただ面倒です。ぼほぼ ① A の下位互換ではないかと話題＠竹下通りです。
use num_traits::Zero; use std::ops::{AddAssign, SubAssign}; fn prefix_sum<T>(h: usize, w: usize, mut f: impl FnMut(usize, usize) -> T) -> Vec<Vec<T>> where T: Zero + AddAssign + SubAssign + Copy, { let mut sum = vec![vec![T::zero(); w]; h]; for i in 0..h { for j in 0..w { let mut x = f(i, j); if i > 0 { x += sum[i - 1][j]; } if j > 0 { x += sum[i][j - 1]; } if i > 0 && j > 0 { x -= sum[i - 1][j - 1]; } sum[i][j] = x; } } sum }
③ B. 高速ゼータ変換の易しいやつで計算する方法
こちらの場合は ① B に比較して特別大変でも楽でもなく、特筆すべきことは特にりません。 ② A とは違って実装上の工夫（1..w, 1..h のところ）により境界値の場合分けがなくせますが、これはデメリットがなくなっただけで、別にメリットが生まれたわけではなしです。
なお注意ですが、コード中の 1..w は $1$ つずらして 0..w - 1 にしたほうがわかりやすくはあるものの、こうすると w == 0 のときに壊れるので注意です。
use num_traits::Zero; use std::ops::AddAssign; fn prefix_sum<T>(h: usize, w: usize, mut f: impl FnMut(usize, usize) -> T) -> Vec<Vec<T>> where T: Zero + AddAssign + Copy, { let mut sum = vec![vec![T::zero(); w]; h]; for i in 0..h { for j in 0..w { sum[i][j] += f(i, j); } } for i in 0..h { for j in 1..w { let x = sum[i][j - 1]; sum[i][j] += x; } } for i in 1..h { for j in 0..w { let x = sum[i - 1][j]; sum[i][j] += x; } } sum }
④ A. 貰うDPで計算する方法
③ A が ① A の下位互換であるのと同様、④ A は ② A の下位互換かもです。場合分けが面倒になっただけと話題＠甲州街道です。
use num_traits::Zero; use std::ops::{AddAssign, SubAssign}; fn suffix_sum<T>(h: usize, w: usize, mut f: impl FnMut(usize, usize) -> T) -> Vec<Vec<T>> where T: Zero + AddAssign + SubAssign + Copy, { let mut sum = vec![vec![T::zero(); w]; h]; for i in (0..h).rev() { for j in (0..w).rev() { sum[i][j] = f(i, j); if i < h - 1 { let x = sum[i + 1][j]; sum[i][j] += x; } if j < w - 1 { let x = sum[i][j + 1]; sum[i][j] += x; } if i < h - 1 && j < w - 1 { let x = sum[i + 1][j + 1]; sum[i][j] -= x; } } } sum }
④ B. 高速ゼータ変換の易しいやつで計算する方法
③ B が ① B に比べて可もなく不可もなくであるのと同様に、④ B も ② B に比べて可もなく不可もなくです。
use num_traits::Zero; use std::ops::AddAssign; fn suffix_sum<T>(h: usize, w: usize, mut f: impl FnMut(usize, usize) -> T) -> Vec<Vec<T>> where T: Zero + AddAssign + Copy, { let mut sum = vec![vec![T::zero(); w]; h]; for i in 0..h { for j in 0..w { sum[i][j] += f(i, j); } } for i in (1..h).rev() { for j in (0..w).rev() { let x = sum[i][j]; sum[i - 1][j] += x; } } for i in (0..h).rev() { for j in (1..w).rev() { let x = sum[i][j]; sum[i][j - 1] += x; } } sum }
長方形和クエリの処理の仕方
上と下それぞれ等号がついているかどうかで 4 種類が考えられますね。AtCoder でよく見るのは 1 番ですが、クエリに $1$ を足したり引いたりして調整をし、累積和①・②で処理しやすい 2 番に帰着するのが良いと思いのではないでしょうか＠もう道路のレパートリーが切れてきました。
- $\displaystyle \sum _ { i0 \le i \le i1, \ j0 \le j \le j1 } A _ { i, j }$
- $\displaystyle \sum _ { i0 \le i \lt i1, \ j0 \le j \lt j1 } A _ { i, j }$
- $\displaystyle \sum _ { i0 \lt i \le i1, \ j0 \lt j \le j1 } A _ { i, j }$
- $\displaystyle \sum _ { i0 \lt i \lt i1, \ j0 \lt j \lt j1 } A _ { i, j }$
① の場合
① が最も得意とする長方形クエリは 2 番の形です。これに帰着しましょう。 この形に帰着したらあとは $B _ { i1, j1 } - B _ { i0, j1 } - B _ { i1, j0 } + B _ { i0, j0 }$ です。
② の場合
② が最も得意とする長方形クエリも実は 2 番の形です。これに帰着しましょう。 この形に帰着したらあとは $B _ { i0, j0 } - B _ { i1, j0 } - B _ { i0, j1 } + B _ { i1, j }$ です。 ところでこれは ① の場合と全く同じ式です。面白いですね。（これは次元 $2$ が偶数だからであって、奇数次元、たとえば $1$ とか $3$ の場合は符号が逆になるため注意です。）
③ の場合
まずこれ基本はおすすめではないのですが、一応ご紹介です。
③ が最も得意とする長方形クエリは 3 番の形です。これに帰着しましょう。（なんですかこの変な形は。） この形に帰着したらあとは $B _ { i1, j1 } - B _ { i0, j1 } - B _ { i1, j0 } + B _ { i0, j0 }$ で、この式も①と同じです。
④ の場合
② と定義域が違うだけなので完全に同じです。これもおすすめではないです。
まとめ
| 質問 | 答え |
|---|---|
| 累積和、前からとるか・後ろからとるか | 基本前から（①, ③）でいのではないでしょうか。用途と好みによっては後ろからでも。どうせほぼ同じコードですし。 |
| ０を追加するか | しましょ（①, ②）う。しない意味はほぼないと思います。 |
| 貰うDPか高速ゼータ変換の易しいやつか | 基本的に貰うDP（A）でよいのではないでしょうか。特殊な状況ではその限りではありませんが。 |
| 長方形クエリの等号について | 下$\le$・上$\lt$ の形に変形するとよいと思います。 |
みなさまのハートフルなリアクションお待ちしております🫶
