ちょっと重いSegTree

http://www.adventar.org/calendars/850の3日目の記事です。

微妙に役に立ちそうで役に立たないSegTreeテクニック

SegTreeで1点を更新するクエリを処理することを考えます。

これはおおむね

  • SegTreeの対応する位置の葉を更新する
  • そこから登っていき, ノードを更新する(そのノードの左右の子の情報をmergeしたものを自分の情報にする)

という2Stepからなります。

たとえばRMQならば上のStepはvalue = x, 下のStepはvalue = min(left->value, right->value)となります。

大体のSegTreeにおいて下のStepの計算量はO(1)ですが、必ずしも定数時間で行う必要はありません。

計算量がO(logN)だとしても、全体での計算量はO(log2 N)に収まります。

つまり下のStepにおいて、その頂点の子になんらかのクエリを飛ばすこともできます。

SegTreeには、

  • 変更クエリ
  • 取得クエリ

を持たせることが多いと思いますが、変更クエリで値を更新していくときにも取得クエリを使うイメージです。

階段状の点を持つ

これは僕が昔出した問題です。(http://yosupo.hatenablog.com/entry/2015/03/09/000435)

  • 点を追加する
  • 点を削除する
  • 点を左上から右下への階段状にしたとき、幾つの点が含まれるか調べる

という3種類のクエリに答える問題です。

階段状の点とは、その点の右上に点がないものを列挙したものです。想像すると階段っぽさがありますね。

点をx座標でsortしてSegTreeで管理するのですが、上記のテクを使うとO(log2 N) / queryで処理できます。

詳しくはURL先を読んでください。

Convex Hull Trick(削除付き)

  • kが与えられるので、直線の中で, x=kにおいてもっともy座標が小さいものを求める
  • 直線を追加する
  • 直線を削除する

というクエリを処理するのを考えます。オフラインクエリです。

このクエリが上記のテクを使えばO(logN)/query(取得, 追加), O(log3 N)/query(削除)で処理できることに気づいたのでこの記事を書きました。

まず、オフラインクエリなので直線を全部列挙しておいて、傾きでsortします。直線をy=ax+bとしたら、左側であるほどaが大きくなるようにします。

その後、その直線列をSegTreeで処理することを考えます。

本質は削除クエリなのですが、とりあえずは取得クエリから考えます。

直線を傾きでsortしておくことにより、非常に良い性質が生まれます。

凸包を想像してもらえれば分かりやすいと思いますが、左右のノードについて、左側のノードに含まれる直線から作られる凸包と右側のノードから作られる凸包、交点が1つしか存在しません。

f:id:yosupo:20151202221248j:plain

なのでノードに持たせる情報は単純明快、この交点のx座標です。

すべてのノードがその交点のx座標を持っていた場合、取得クエリはとても簡単になります。

そのx座標が求めたい座標より大きいなら左、小さいなら右のノードに再帰的に潜っていけばいいだけです。

最終的に到達した葉が持つ直線が求める直線です。

では、次に追加/削除クエリを考えます。

もちろん重要なのはノードのmergeです。これをO(log2 N)で処理します。これができれば追加、削除クエリがO(log3 N)で処理できます。

要するに交点の座標を求めれば良いのですが、これは簡単で、x座標で二分探索をします。二分探索をしてその座標では左右のノードのどちらの方が大きいかを求めれば良いですが、これは左右のノードに対して取得クエリを飛ばせば良いです。

これでクエリの計算量はO(log2 Nlog(座標/eps))になりました。あとはちょっと頑張るとO(log3 N)になります。 追加クエリは頑張るとO(logN)になります。ならないかも。

本当はもう一個logが落ちてくれたら出題したかったのですが、O(log3 N)では微妙なため供養します。

頑張ったらもう一個ぐらい落ちてくれるかもしれません。ぜひ考えてみてください。

ちなみに平方分割だとO(sqrtN)で解けます。

他の例

もう一個ぐらい考えたかったけど特になかったです。

明日はantaさんの記事です。楽しみですね