平衡二分探索木 Treap と Splay の実装と応用
平衡二分探索木（Balanced BST）は、動的集合操作を効率よく扱うための重要なデータ構造である。特に Treap および Splay 木は、それぞれ異なる戦略で平衡性を保ちながら、挿入・削除・検索などの基本操作を平均 $O(\log n)$ 時間で実現する。
単回転 Treap
Treap（Tree + Heap）は、各ノードにランダムな優先度（priority）を持たせ、二分探索木の性質とヒープの性質を同 ...
7月24日 03:15 投稿
CodeForces 85D: Sum of Medians の多角的なアプローチと実装
本記事では、CodeForces 85D - Sum of Medians という問題に対する4つの異なる解法を解説します。この問題は、動的な集合に対する要素の追加、削除、および特定の位置にある要素の総和を求めるクエリを効率的に処理することを求めています。
問題概要
空の集合 S に対して、Q 個のクエリが与えられます。各クエリは以下の3種類のいずれかです。
add x: x \in [1, 10^9] ...
6月3日 16:44 投稿