ngtkana https://blog.hatena.ne.jp/ngtkana/ ブログ名 https://ngtkana.hatenablog.com/ 区間ヒープってバグりますよね。わかります。 概略は簡単なのですけれども長さを $4$ で割った余りで謎の場合分けが入ってつらい印象です。 この記事では私が簡単かつ高速であると思っている実装をご紹介していきます。 データ表現 この辺りは基本的にご存じな前提でお話を進めたいのですが、認識をそろえるために簡単にご説明します。 区間ヒープは根が最大値・最小値を持ち、残りを左の子・右の子で任意に半々（奇数ならば左が多い）に分割して管理するヒープ型木データ表現です。つまり各節点が基本的に $2$ 個（要素数が奇数のときは末尾だけ $1$ 個）の要素を管理する二分木の形をしていて、かつその節点の管理する $… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fngtkana.hatenablog.com%2Fentry%2F2024%2F04%2F05%2F025152" title="区間ヒープのバグらせない実装だと思っているものを公開します - ブログ名" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/n/ngtkana/20240404/20240404220519.png Hatena Blog https://hatena.blog 2024-04-05 02:51:52 rich https://ngtkana.hatenablog.com/entry/2024/04/05/025152 1.0 100%