伝家の宝刀 クエリ平方分割について

はじめに

 本記事は、競プロアドベントカレンダー2020 の12/15分の記事です。ネタに困っていたんですが、Twitter上でクエリ平方分割に関する記事がほとんどないという声を見て、殴り書きではありますが本記事を作成することにしました。易しい問題を例にクエリ平方分割を使った解法の例を示した後、いくつか少し手間のかかる問題を見ていきます。実装量がある程度かさむことになりがちなので、自分で一から実装することをお勧めします。想定読者層としては水~青色を想定しています。

クエリ平方分割とは

  クエリ平方分割というのは、その名の通り、与えられたクエリを(その数をQとします)O(\sqrt{Q})ごと1に分割してクエリをうまく処理すると、なぜか計算量がo(NQ)に落ちる2というテクニックです。例えば、長さが Nの配列に関するQ個のクエリが与えられたときに、次のような処理をしたとしましょう。

  • Q個のクエリをO(\sqrt{Q})個ごとに分割すると、全部でO(\sqrt{Q})個のブロックができる。
  • 各ブロックごとに、次のようにする。
    • まず、O(N)で何らかの前処理をする
    • 各クエリを、同一ブロック内のクエリだけを見てO(\sqrt{Q})で処理する。

このときの計算量を考えます。まず、O(N)の処理をする回数はO(\sqrt{Q})回です。さらに、各クエリの処理にO(\sqrt{Q})かけているので、クエリの処理自体にかかる計算量はO(Q\sqrt{Q})です。よって、全体の計算量はO(N\sqrt{Q}+Q\sqrt{Q})となり、たしかにo(NQ)となっています。ちょっとした工夫しかしていないのに、ちゃんと計算量が落ちるところがこのテクニックの面白いところだと思います。このテクニックを適用する際は、「ブロック内の処理の初めに どのような前処理をすれば、各クエリO(\sqrt{Q})で処理できるようになるか?」を考えることになります。
 それでは、クエリ平方分割の適用例を紹介していきます。

クエリ平方分割の適用例

ABC185 : Range XOR Query

 最近出題されたABCの問題を例にとります。この問題はSegment Treeを使って解くことができますが、あえてクエリ平方分割で解くことを考えてみましょう。

 各ブロックに対する処理を考えます。まずクエリの処理の前に、この時点での配列の累積xorを計算しておきます(O(N))。クエリの処理では、更新クエリでは元の配列を単に更新するだけです。解答クエリは、まず累積XORの情報から該当区間の値を取得します。その後、現在のブロック内における自分より前の更新クエリを見に行き、該当区間に更新があればその変更を答えに反映します(xorをとるだけ)。クエリを分割したことで、更新の影響を愚直にO(\sqrt{Q})かけて確認してよいところがクエリ平方分割の利点です。

 実装例はこちらですが、累積xorをブロックの処理の最後に取るなど上記の説明と少し順番を変えています。

 ところで、ブロック内の処理では次のような方法も考えられます。最初に累積xorをとるところは同じです。その後、ブロック内のクエリに登場するindexを覚えておきます。このindexとして考えられる値はO(\sqrt{Q})個しかありません。このindexたちを座標圧縮し、適切にもとの配列の情報を載せれば3、長さO(\sqrt{Q})の配列が完成します。ここまでやってしまえば、各クエリの処理を愚直に行っても毎回O(\sqrt{Q})で終わり、先ほどと同じ計算量のオーダーが達成されます(前処理の定数倍が重いですが)。実装例はこちら

 このように、各ブロック内でクエリが関わる位置がO(\sqrt{Q})個しかないことを利用して、O(\sqrt{Q})個の配列に圧縮してからあとは愚直にやる、という流れもクエリ平方分割の適用の1つです。しつこいですが、どのような前処理をすればブロック内のクエリの処理を\sqrt{Q}で終えられるか?ということを考えるのは、クエリ平方分割の肝と言えるでしょう。

パ研合宿2019 Day-2-G:Bichrome Tree Connectivity

 クエリを平方分割し、ブロック内の処理を考えます。ブロック内ではクエリが飛んでくる頂点がO(\sqrt{Q})個しかないことに注目して、木を圧縮して頂点数がO(\sqrt{Q})個の森にすることを考えます。クエリが飛んでくる頂点はそのまま残します。そうでない頂点のうち、黒い頂点はそのブロック内では黒いままなので残しません。白い頂点は、まず白い頂点だけからなる各連結成分を1つに圧縮し、その元々のサイズを覚えておきます。そして、圧縮した1つの頂点と、その連結成分に隣接するクエリが飛んでくる点を辺で結びます。このようにすると森が完成しますが、ウニのようなケースで頂点がO(N)個になってしまう可能性があります4。そこで、圧縮した頂点のうち、次数が1のものは、その頂点と結ばれているクエリが飛んでくる頂点にマージしてしまいます。このようにすると、この森の頂点数がO(\sqrt{Q})になることが示せます。
 クエリの処理は、更新も解答も愚直にやるだけでO(\sqrt{Q})となります。実装例はこちらです。

困った時のクエリ平方分割

 想定解とは異なっていても、ブロックサイズの調整と定数倍高速化を頑張ることで、クエリ平方分割で通せる場合があります。

JOI2016春Day2 : 雇用計画

 想定解はO ( (N+Q) \log N)だったと思いますが、クエリ平方分割で解くことを考えます。
 両端に-\inftyを入れておきます。B_jが与えられたときの答えは、B_j以上の数からなる区間の個数ですが、代わりに区間の境界の数を考えることにします。クエリを平方分割し、ブロックごとの処理を考えます。N+1個の境界について、今のブロック内について区間の境界となり得るようなB_jの値は区間をなしているので、B_jをソートしておけば二分探索+imos法で各境界の解答クエリのへの寄与を加算することができます。あとは各更新クエリの度に、影響のある解答クエリの答えを再更新すればよいです。前処理にlogがつくこともあり、ブロックサイズの調整と定数倍高速化を頑張るとACできます。
 実装例はこちらです。TL5secなのでギリギリです。

その他の問題

 見つけたら随時追加します。

おわりに

 クエリ平方分割について簡単に紹介しました。クエリ平方分割が想定解という問題ももちろんありますが、非想定でもクエリ処理の問題で困った時になんとかする方法としても有力です。ご使用の際にはブロックサイズの調整にご注意ください。


  1. 実際はブロック内での処理にlogがついてるかとか、定数倍がどうかで1ブロックあたりのクエリ数をいくつにするかを調整したりします。

  2. o(f(n))というのはオーダーがf(n)未満というイメージです。

  3. 具体的には、クエリに登場するindexをソートした配列をb_1,b_2,\cdots,b_nとして、 A_{b_i}, \cdots , A_{b_{i+1} - 1}をxorした値を持っておきます。

  4. ウニの中心にしかクエリが来ていない状態でこれをやると…?