std::set要素をソートされた順序で格納するc++ では、 O(log n) 時間で要素を挿入できます。しかし、私が知っているすべての方法は線形時間がかかります:
配列の最後に要素を挿入し、前の要素がそれよりも小さくなるまで前の要素と交換するには、線形時間がかかります。
配列でバイナリ検索を使用して、挿入する要素の位置を見つける: O(log n) 時間かかりますが、指定された位置に要素を挿入するには、最悪の場合 O(n) 時間がかかります。
ソートされた配列をヒープとして使用すると、O(log n) 時間で要素を挿入できますが、その後配列がヒープのままであっても、ソートされたままであるという保証はありません。
O（log n）時間でソートされた配列に要素を挿入する方法が必要です。これが可能であることはわかってstd::setいますが、方法はわかりません。