エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
【Python】平衡二分木が必要な時に代わりに何とかするテク【競プロ】 - Qiita
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
【Python】平衡二分木が必要な時に代わりに何とかするテク【競プロ】 - Qiita
などの操作が可能で、C++ではstd::setやstd::map等の連想コンテナの実装に用いられています。 このstd::... などの操作が可能で、C++ではstd::setやstd::map等の連想コンテナの実装に用いられています。 このstd::set, std::mapというのは優れもので、標準ライブラリ中のデータ構造でありながら lower_bound(x): $x$ 以上の最小の要素 upper_bound(x): $x$ 以下の最大の要素 を$O(\log N)$で計算することができます。集合が内部的に常にソートされているので、二分探索ができる、と考えると分かりやすいかと思います。この手軽さゆえに、競技プログラミングの問題の解説に 「……よって、平衡二分木(C++ではsetなど)を使うことで解くことができます。」 と書かれていることがしばしばあります。 残念ながら、Pythonにはそのような組み込みのデータ構造が存在しないため、解説の通りにコードを組むことができません。そこで本記事では、平衡二分木が欲し