セグメント木
競技プログラミングでよく使われるデータ構造として、セグメント木というものが存在します。 競技プログラミングを始めるとまず、BIT（Binary Index Tree）というものを知って感動することになります。 そしてその一般化として、セグメント木を知ることになります。
セグメント木とはどういうデータ構造かというと、
- 配列のようなデータ構造である
- データとしては単位元と二項演算を定義した値（モノイド）をとることが出来る
- [i]をO(logN)で更新する
- [i,j)に対する範囲クエリをO(logN)で計算する
ことが出来るデータ構造です。 例えば、ある範囲の最小値を計算させるようにも出来ますし、合計値を計算させるようにも出来ます。
この記事は、セグメント木については知ってることを前提とします。
2次元セグメント木
これを2次元に拡張して、以下のようなデータ構造を考えます。
- HxWの2次元配列のようなデータ構造である
- [i][j]をO(logHlogW)で更新する
- [i0,i1)x[j0,j1)に対する範囲クエリをO(logHlogW)で計算する
このようなデータ構造があると、
を解くことが出来ます。 というか、この問題で2次元セグメント木というものを学んで、 感動したのでこの記事を書いています。 自分で2次元セグメント木を実装して、 実装がナイーブな（セグメント木の更新・クエリに関わるノードを計算する部分を分離する原理主義的な実装をしました。そのため境界でオーバーヘッドが生じています） 割にはまぁまぁの実行時間では解けたので、理解自体は正しいと思います。
空間O(HW)の実装
他にも実装の方法はあるようですが、 今回は、「セグONセグ」という方法で実装します。
HxWの2次元セグ木を、大きさHのセグ木の書くノードに大きさWのセグ木が入ってると考えることにしましょう。 図は、2x5の2次元セグ木の様子を表しています。 また簡単のため、モノイドの実装はunit=0, op=maxとします。
更新
このデータ構造において、更新時はSEG[i][j] = max(SEG[2i][j], SEG[2i+1][j])のように ルート方向に伝搬させて更新させることにします。 すると、あるブランチのSEG[i][j]は、その子孫のSEG[*][j]のmaxを持ってることになります。 更新に関わるH方向のノード数がO(logH)で各ノードでO(logW)の更新が行われるのでトータルでO(logHlogW)です。
クエリ
クエリは簡単です。 まず、H方向でクエリ[i0,i1)に関わるノードをマークして、 各々のノードで範囲クエリ[j0,j1)を行えばよいです。 H方向のノード数がO(logH)で、各ノードでO(logW)なのでトータルでO(logHlowW)です。
このアイデアに基づけば、2次元セグ木が実装出来そうです。
メモリ使用量の工夫
少しだけですが、メモリ使用量を工夫してみましょう。 問題によっては、HxWのマスすべてを使うのではなく、すごく疎な場合があります。 そして、結果としてどのマスを使うかが先にわかる場合、メモリ量を節約することが出来ます。
以下の図は、全10マスのうち、[0][0],[0][4],[1][1],[1][4]の4マスしか使わない場合を表しています。
こういった場合、各ノードのセグ木を緑色のマス数だけに節約してしまい、 補助的なデータ構造として、マスの対応関係を保存（配列で良い）しておけば、 論理的には、上で述べた実装の工夫なしの場合と同じことが出来ることになります。
ただし、マスの対応関係というワンクッションがあるために、 二分探索が都度必要になります。 しかし、これはO(log緑のマス個数)であり、 各ノードでは更新・クエリに関わらずどの道セグ木のO(log緑マス個数)がかかりますから、 オーダーに影響しません。