読者です 読者をやめる 読者になる 読者になる

平衡二分木を使う問題

平衡二分木は、定数倍は遅いしコード長がアホみたいに長くなりますがとても強力なデータ構造です。
そんな平衡二分木を使う事が最近多いので、使った問題を紹介します。

木の種類

RBST
軽実装かつコピー可能な(追記:不可能です。)プロコンなら最強感のある木
とりあえずコレを書いておけば困る事はあんまり無さそう
実装、解説はiwiwi大先生のスライドが良かった
プログラミングコンテストでのデータ構造 2 ~平衡二分探索木編~

AA Tree or LLRB Tree(Left Leaning Red Black Tree)
insert/eraseだけの実装なら簡単
merge/splitの実装は面倒
reverseの実装は闇
insert/eraseの定数倍はRBSTより速い、僕の実装では

Red Black Tree
実装は面倒だけど、reverseに関してだけはAA Treeよりも簡単だと思う。書いたことはないしこれからもなさそう

Splay Tree
実装は軽い 再アクセスが高速 Link-Cut Treeに使用 コピーは厳しい
これも強い木
永続化とコピーは出来るのかなぁ
実装はqnighyさんのスライドとコードが非常に良かった
スライド
http://www.ioi-jp.org/camp/2013/2013-sp-tasks/2013-sp-day4-spaceships-review.pdf
コード
http://www.ioi-jp.org/camp/2013/2013-sp-tasks/2013-sp-day4-spaceships-sample2.cpp

基本的にSplay操作さえ実装してしまえば色んな事(merge,split,insert,delete)が出来るため強い。

Link-Cut Tree
上のqnighyさんのスライドとiwiwi大先生のスライドが大変素晴らしい
プログラミングコンテストでのデータ構造 2 ~動的木編~

平衡二分木

ARC33 C問題

C: データ構造 - AtCoder Regular Contest 033 | AtCoder
k番目にアクセスできるsetが必要。BITは知らない。

AOJ1508 RMQ

RMQ | Aizu Online Judge
数列を平衡二分木で扱う問題の中で基本的なやつ。
平行分割は知らない。

上2問は平衡二分木を初めて書く人向け。

CodeFestival エキシビジョンB カッコつけ

B: カッコつけ - CODE FESTIVAL 2014 エキシビション(オープン) | AtCoder

遅延評価平衡二分木

ICPC東京2013 Longest Chain

Longest Chain | Aizu Online Judge

想定解法は、点を常に階段状になるように削ることで達成していますが、平衡二分木を使っても解けます
平衡二分木解は結構面白いと思います

CODE FESTIVAL 本戦 I Shapes

CODE FESTIVAL 本戦 I - Shapes - よすぽの日記

平面走査フェーズで利用可能

永続SegTree

CF #260 Div1E Function

Problem - E - Codeforces

永続平衡二分木

ARC30 D グラフではない

D: グラフではない - AtCoder Regular Contest 030 | AtCoder

遅延評価+永続 面倒

Link Cut Tree

そもそも問題数が少ない

HackerRank Weekly 12 White Falcon

HackerRank Weekly12 White Falcon - よすぽの日記

Do use segment tree

みんな大好きDo use segment treeだよ(^^)/~~~
Do use segment tree | Aizu Online Judge