平方分割の練習をしようにも難しい問題ばかり、そんなお悩みに狙いを決めて手取り足取りのレクチャーです！
ちなみになのですが、「気になる💓あの子を平方分割！列の区間和を求める恋の特効薬アルゴリズムを、幸運なあなただけにご紹介です。」というタイトルは没になりました。（← これはタイトルでふざけすぎて怒られたのに懲りずにこっそり本文でサルベージする人です。）
対象の読者さん紹介です。
当記事は、平方分割にあまりなれていない方が、簡単なものであれば息を吸うようにスラスラかけるようになるのが目的です。したがってですね……
カモンです。
- 平方分割の実装は大変そうです。
- 練習のやり方がわかりません。
ノー・カモンです。
- 遅延評価のない平方分割なんて……
- 親に重めなデータ構造を持たせるのが醍醐味ですよね〜〜
- クエリ平方分割で常勝！ｗ
どのように練習するのが良いでしょう。
おすすめな練習方法です
まず、だめなパターンです。
- 平方分割が大活躍する問題で練習します。
これはだめです。正しくはこうです。
- どうにでも解けそうなものを、平方分割で解きます。
いいですか？ 欲張ってはいけません。まずは使わなくても良いところでもどんどん使って練習していきましょう。 平方根は定数です。適切な場面でだけ使うのは、なれてきてからで良いでしょう。ひたすら素振りです！
おすすめの問題です。
入門におすすめなのは Range Sum Query です。実装に挑戦してみたい方は、Aizu Online Judge に練習問題（ 🔗aoj-dsl-2-b） がありますから、こちらに挑戦してみると良いです。
どうして Range Sum Query で練習するのがよいでしょう。
理由は 2 つあります。まず 1 つ目に、簡単だからです。平方分割は難しくありません。難しい問題でよく使うので、難しく感じるだけなのです。まずは簡単な問題で使ってみて、「平方分割自体は難しくない」ということを覚え、本質部分をサッとかけるようにしましょう。
2 つ目に、重なるのですが、デバッグがしやすいからです。難易度だけで言えば Range Minimum Query などでもよさそうなのですが、こちらは答えの情報量が少ないですから、デバッグがしづらいがちです。最適化よりも数え上げのほうが、嬉しいですよね。
Range Sum Query さんを平方分割です！
先程もリンクをいたしましたが、再びです。（🔗aoj-dsl-2-b）
概要です。長さ $N$ の列があります。リンク先の問題では、これははじめは $0$ で初期化されているのですが、そうではなく任意の初期値で考えましょう。。ここに 2 種類の クエリです。
- クエリ 1: $a _ i$ を $x$ 増加させます。
- クエリ 2: $a _ l + \dots + a _ { r - 1 }$ を計算です。
愚直だいすきクラブのコーナーです
まずは愚直を書きましょう。無駄にはなりません。各クエリは次のように処理です。
クエリ 1 です。これは、$a _ i \leftarrow a _ i + x$ のように代入をすると良いです。
クエリ 2 です。普通は C / C++ でいう for (int i = l; i < r; i++) のようなことをするでしょうが、今回は i を使わずに書いてみましょう。
- まずは新しい変数 $\mathtt{ ans }$ に $0$ を格納します。
- $l$ が $r$ と異なる限り次のことを続けましょう。
- 俺のターン、ドローです！ $\mathtt{ ans }$ に $a _ l$ を足します。そのあと $l$ を $1$ だけ増加させて、ターン終了です。（どやぁ）
図解をしましょう。これは $l = 1, r = 4$ のときの図です。それでは皆さんの両手を拝借です。いいですか？ 左手を [ に、右手を [ に添えましょう。（はい？）
$$ \begin{array}{rrrrrrrrrrrrrrrrrrrrrrrrr} a = & (& 10, \ \big[ 30, \ 20, \ 50, \big[ \ 40 & ) \end{array} $$
繰り返しの $1$ 回目が終わると、$l$ が一つ増えて、もともと $a _ l$ だったものが答えに足されることになります。C / C++ でいうところの、ans += a.at(++l) です。
$$ \begin{array}{rrrrrrrrrrrrrrrrrrrrrrrrr} a = & (& 10, \ 30, \ \big[ 20, \ 50, \big[ \ 40 & ) \end{array} $$
もちろん逆からでもよいです。では先程の疑似コードとは異なりますが、ここから今度は $r$ を減少させましょう。すると、今度は新しく $a _ r$ になったものが答えにたされることになります。C / C++ でいうところの、ans += a.at(--r) です。
$$ \begin{array}{rrrrrrrrrrrrrrrrrrrrrrrrr} a = & (& 10, \ 30, \ \big[ 20, \big[ \ 50, \ 40 & ) \end{array} $$
愚直イヤイヤ期のみなさんにお送りする、スンマートなアーウゴリーズンです。
数列 $a$ を、$k$ 個ごとに分割です。部分和 $b$ を前計算しておくと、このようになります。しかしただ前計算するだけではいけません。クエリ 1 が来るたびに、配列 $b$ も更新していきましょう。
$$ \begin{array}{rrrrrrrrrrrrrrrrrrrrrrrrr} a = & (& 10, \ 30, & |& 20, \ 50, & |& 40 & ) \\ b = & (& 40, & |& 70, & |& 40 & ) \end{array} $$
難しいのはクエリ 2 です。しかしみなさんには手が 2 本ありますね。これは我々人類がうなぎよりもアルゴリズムが上手であることを示唆しています。存分に活用しましょう！
右手左手の準備はよろしいですか？
まずは手の置き場所を決めましょう。数列の隙間に失礼して、求めたい区間を両手ではさみましょう。小さすぎると難しいですから、少し大きめな数列にしましょう。また、添字に言及するのも億劫ですし、値も $0, 1, 2, \dots$ にしてしまいましょう！ これは、$l = 1, r = 10$ のときの図です。
$$ \begin{array}{rrrrrrrrrrrrrrrrrrrrrrrrr} a = & (& 0, \ \big[ 1,\ 2, & |& 3, \ 4, \ 5, & |& 6, \ 7, \ 8, & | & 9, \big[ \ 10 & ) \\ b = & (& 3, & |& 12, & |& 21, & | & 19 & ) \end{array} $$
大筋は先ほどと同じです！ 左手と右手を近づけていって、ぺったんこをしたら、ゲーム終了です。みなさんの両手は、両思いです。
ただ近づけるだけではいけません。ここが平方分割のスマート・ポイントなのですが、一気にできるところは一気に足しましょう！ アルゴリズムは 3 段階に分かれます。
- おそるおそる左手を近づけてポジショニングです。
- おそるおそる右手を近づけてポジショニングです。
- おりゃーーです。
まずは 1, 2 です。やり方は先ほどと同じなのですが、どれくらい近づけると良いのでしょう。おりゃーーーができるまで近づけましょう。これで $l = 3, r = 9, \mathtt{ ans } = 11$ です。ぐっと睨むと、$l$ と $r$ が $k = 3$ の倍数になっていることがわかります。プログラムを書くときには、これを目印にしましょう！
$$ \begin{array}{rrrrrrrrrrrrrrrrrrrrrrrr} a = & (& 0, \ 1,\ 2, & |& \big[ 3, \ 4, \ 5 & |& 6, \ 7, \ 8, & | & \big[ 9, \ 10 & ) \\ b = & (& 3, & |& 12, & |& 21, & | & 19 & ) \end{array} $$
おたのしみ、おりゃーーのコーナーです。
疑似コードはこうです。
- $l$ が $r$ と異なる限り次のことを続けましょう。
- $\mathtt{ ans }$ に $b _ { l / k }$ を足します。（この添字は整数になります。）
図解です。$l$ を $3$ 増やすとこうです。$\mathtt{ ans }$ には、$3 + 4 + 5$ が足されるのですが、$b _ 1 = 12$ を見るのがスマートです。次の一手でトドメがさせるのですが、デキるアルゴリズマーは背中で語ります。最後はみなさんでどうぞです。
$$ \begin{array}{rrrrrrrrrrrrrrrrrrrrrrrrr} a = & (& 0, \ 1,\ 2, & |& 3, \ 4, \ 5, & |& \big[ 6, \ 7, \ 8, & | & \big[ 9, \ 10 & ) \\ b = & (& 3, & |& 12, & |& 21, & | & 19 & ) \end{array} $$
ごめんな、父さんな、コーナーケースなんだ……
今まで黙っていたのですが、先程のアルゴリズムをそのまま実装するのではだめな場合がります。第 1 段階と第 2 段階に注目です。左手と右手は、$k$ で割ったあまりだけを頼りに突き進んでしまいます。たとえばこちらの場合、$l = 7$ は $9$ まで進み、$r = 8$ は $6$ まで進み、二人の思いはすれ違いです。最悪の場合、$l$ は地平線の果てまで負い続けて、ついには……です。こういった悲しい事故をなくすためにも、$k$ で割り切れるかどうかだけでなく、$l = r$ かどうかを必ずチェックです。（画像：Flat Earth - Wikipedia）
$$ \begin{array}{rrrrrrrrrrrrrrrrrrrrrrrrr} a = & (& 0, \ 1,\ 2, & |& 3, \ 4, \ 5, & |& 6, \ \big[7, \big[ \ 8, & | & 9, \ 10 & ) \\ b = & (& 3, & |& 12, & |& 21, & | & 19 & ) \end{array} $$
実装です。
C++ ならば、こうです。まずはブロックサイズと、ブロックの数です。
int k = std::sqrt(n), q = (n + k - 1) / k;
クエリ 2 だけで良いでしょうか。1 のほうは、背中で語ることにしようと思います。
int ans = 0;
for (; l < r && l % k; ans += a.at(l++));
for (; l < r && r % k; ans += a.at(--r));
for (; l < r; ans += a.at((r-=k) / k);
ご挨拶
いかがでしたでしょうか。
みなさまの平方分割ライフが、より豊かで快適なものになるよう、願っております。ツイッター・インスタグラムはこちらです。それではまたのご視聴をお待ちしております。ばいばーい👋（← これは言ってみたかっただけの人です。）
