配列に対して一連の範囲更新を実行する必要があります。つまり、範囲に定数を追加したり、範囲から定数を減算したりする必要があります。その後、最終的な配列のRANGE、つまり（max-min）を見つける必要があります。最初の番号は1からnです。
バイナリインデックスツリーを使用しています。各更新はログNにあります。このように、O（n）以下の時間でRANGE（またはmaxとmin）を見つける方法があるかどうかを知りたいです。従来は、O（n log n）を取ります。
3 に答える
0
配列を一度だけ並べ替えてみませんか？次に、配列全体から定数を加算または減算すると、正の数を乗算する場合と同じ順序になります。たぶん、絵にはもっと多くのものがあります。
于 2012-08-07T23:36:18.673 に答える
0
増分更新を行うために配列要素にアドレス指定する必要があるため、配列要素への直接のインデックス アクセスが必要です。
また、最小ヒープと最大ヒープを維持する必要があります。
要素を更新するときは、2 つのヒープ内の対応するエントリも更新する必要があります。したがって、配列内の 2 つのヒープ内の対応する要素にポインターを格納する必要があります。
元のヒープの作成は O(n) で、変更は O(lg(N)) です。
于 2012-08-07T19:47:00.050 に答える