問題タブ [rmq]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
algorithm - フェンウィック木一括更新
フェンウィック ツリーには update(idx, delta) 関数があり、次のように実装できます。
したがって、現在の idx を更新してから、変更を最後までプッシュします。
次のように、ループ内でいくつかの更新呼び出しを実行したい
更新されるインデックスの範囲 (ここでは 12 - 17 ) が事前にわかっている場合、更新が最適化される可能性があります。毎回最後までプッシュするのではなく、特定のインデックスまでプッシュして残りの変更をバッファリングし、最後の更新後にバッファリングされた変更を最後までプッシュすることができます。概念を説明する図の提供:
たとえば、範囲 3 - 7 を取ります。
インデックス 3 を更新すると、次のインデックスが更新されます: 3 - 4 - 8 - 16。
インデックス 4 を更新すると、次のようになります: 4 - 8 - 16
の更新インデックス 5 は次のようになります: 5 - 6 - 8 - 16
すべてを 8 までプッシュし、残りをバッファリングしてから 16 までプッシュするのが最適です。
質問
範囲の開始と終了を知っていて、このノードを (ここでは 8 ) までプッシュするより良い方法はありますか?