要求
<ul>
<li>削除可能な集合${x}$から不等号で表現された条件$x \ge x_0$を満たすものを列挙したい</li>
<li>例えば<a href="/ja/%E3%82%BD%E3%83%BC%E3%83%88%E6%B8%88%E3%81%BF%E9%85%8D%E5%88%97">ソート済み配列</a>なら<a href="/ja/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2">二分探索</a>で不等号条件を満たす境界を対数オーダーで見つけられる<ul>
<li>しかし配列からの削除は線形オーダー掛かってしまう</li>
</ul>
</li>
<li>削除が高速な<a href="/ja/%E3%83%AA%E3%83%B3%E3%82%AF%E3%83%88%E3%83%AA%E3%82%B9%E3%83%88">リンクトリスト</a>では、ランダムアクセスができないので二分探索できない</li>
</ul>
解法
<ul>
<li><a href="/ja/%E3%83%95%E3%82%A7%E3%83%8B%E3%83%83%E3%82%AF%E6%9C%A8">フェニック木</a>を使う</li>
<li>値域は0/1で、値の存在不在を表現</li>
<li>x0以下の範囲に対する和sを対数オーダーで計算し、それから和がs+1になる点を対数オーダーで二分探索すれば良い</li>
</ul>
<a href="/ja/%E5%89%8A%E9%99%A4%E5%8F%AF%E8%83%BD%E9%9B%86%E5%90%88">削除可能集合</a>で<a href="/ja/%E4%B8%8D%E7%AD%89%E5%8F%B7%E6%9D%A1%E4%BB%B6">不等号条件</a>
<a href="/ja/%E5%95%8F%E9%A1%8C%E5%A4%89%E6%8F%9B">問題変換</a>

削除可能集合で不等号条件