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つしか存在しません。
なのでノードに持たせる情報は単純明快、この交点の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さんの記事です。楽しみですね