antaのWeb日記

あくまで日記として

range treeとか(segment treeとかにΘ(その区間サイズ)の構造全部乗っけちゃうやつ)

警告:全く実装してないので信頼性低低。結構間違っていそう!そのうち実装してみてその時また書く。

なんかマイナー?。実際自分も覚えてなかった。

d次元ならsegment treeのsegment treeのsegment treeの…っていうふうにすればよい。(実際には~3次元くらいしか使えなさそう。メモリが…あと全探索より遅くなる)

G番目の数字とかこれでもいけそう。log^3ではメモリやばそうだけどWaveletMatrixをsegment treeに乗せればlogを2個にできると思う(確認・実装してないから結構弱い「たぶん」だけど…)。

空間はΘ(n log^d n)となる。まあ当たり前なんだけど、豪快なわりに、という感じで。結構今までその感覚が無くて考えてなかった。空間の定数倍は無い(乗せるデータのサイズだけ)ので結構いけそう。

時間はΘ(log^(d-1) n)が掛け算される。データをマージして処理する必要があるから、乗せるデータ構造によって上手くいかない可能性がある。

segment treeなんだけど今回は静的なクエリ問題重視。動的なものにも適用できるけれど、データ構造がまた動的な変更に対応している必要がある。

ベースはsegment treeだけじゃなくて平衡木にも適用できる可能性がある。でもデータ構造が動的なマージに対応してないと大変なことになる気がするから上手くいかないと思う。

sorted配列

たとえばその区間の値をソートした配列を乗っけちゃう。名前、ありそうだけど不明。

見た目がmerge sortそのままである。実際構築はmerge sortの途中の配列も残しとく感じでΘ(n log n)。

すると区間内のx以下の数の数え上げクエリ、つまり「2次元」クエリがΘ(log^2 n)でできる。やり方:各ノードに対してx以下の数を二分探索で数えて足す。

区間内のk番目の数クエリは単純には二分探索すればΘ(log^3 n)だけれど…。

Fenwick tree / segment tree / 平衡木

区間内k番目の数Θ(log^2 n)?

各segment treeはそのsorted 区間の列を持つ…としたらうまくいかない。マージ上でΘ(log n)でやる場合には、値自体(全体でのインデックスで大きさnに圧縮できる)を分割する感じで揃えなければいけない。値→boolフラグを持って、そのフラグの数をノードが持つやつ。

でも、全部が全部その構造を単なるsegment treeで持ったら、今度はサイズが全体でΘ(n^2)になってしまう!

これは動的にノードを作ることで解決できる。ただし…まだサイズに注意。今度は単純にΘ(n log n)とはいかない…?なぜなら、動的にしてもなおsegment treeのノード数がその区間の幅ではないから。O(n log^2 n)ではあるが…lower boundはどうだろ。少し考えたらわかる気もするけど…?不明。考えるべき。

動的更新

各ノードのデータ構造を動的に更新することもできる、と思う。

ただし、例えば値の書き換えならば値でインデックスされた動的segment treeか平衡木が必要、と思う。

あと、動的な下から上へのupdateが実際にはΘ(n)とかかかって行えないので、更新のたびに適切に処理する必要がありそう。

あと遅延伝播(lazy propagation)は難しそうだができないことはなさそう?

コメント

"?"ばっかりで内容が無いよう。そのうち実装する。

自分が今まで全く考えられていなかったので。一応有名なプログラミングコンテストでのデータ構造の最後にも少し記載あるのだけれど、全然気に留めていなくて。

問題作りとしては、結構マイナー?なので結構できそう?。乗せる構造を工夫したり更新を工夫したら面白くなりそう。

ポイントとして、このデータ構造は「建前上」segment treeとかのパーツの知識だけで実装できるということ。そのおかげで出題しやすいかもしれない。関係ない話として:よくそういう考え方あるけれど、あくまで建前だなあとか個人的には思う。