まずこちらをご覧ください。 RBSTがコピー可能は嘘という疑惑 - よすぽの日記 これをちょっと変更すると以下のコードになります。 このコードを実行すると木の高さが5000近くに到達すると思います。 gist.github.com これを利用して、AtCoderのグラフではな…

コピー可能なRBSTを持っている人は以下の疑似コードっぽい動作をやってみてください。多分結構な確率で高さが300を超えます。 gist.github.com 永続が必要な時は赤黒木とか使うと良さそうです

はじめに この記事はHL分解について書きます。 HL分解+SegTreeでパス上のクエリに答えると、最悪ケースで O(log2 N) per query ですが、これを O(logN) per query に改善したいと思います。 アイデア HL分解の詳細についての解説は省きます。たくさんネット…