問題タブ [fenwick-tree]
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 - フェンウィック ツリーとセグメント ツリー
配列の範囲内で合計を計算する必要があったため、Segment Tree と Fenwick Tree に出会い、これらのツリーの両方が同じ漸近的な実行時間でクエリと更新を行っていることに気付きました。もう少し調査を行ったところ、これら 2 つのデータ構造はすべてを同じ速度で実行しているようです。どちらもメモリ使用量は線形です (セグメント ツリーは 2 倍使用します)。
実行時間/メモリと実装の一定の要因は別として、どちらかを選択する理由はありますか?
私は客観的な答えを探しています。たとえば、一方が他方よりも高速な操作や、一方が他方にない制限があるなどです。
これについて他に 2 つの StackOverflow の質問を見ましたが、回答では、一方が他方よりも優れている場合を説明するのではなく、両方のデータ構造について説明しただけです。
sorting - フェンウィック ツリーを使用した部分配列の合計の計算
問題があり、フェンウィック ツリーで解決できるかどうかわかりません。問題は次のとおりです。元の配列 a = [8,4,7,0] があります。ここで、配列を反復処理し、各ステップで次のような並べ替えられたサブ配列に関心があります: [8]、[4,8]、[4,7,8]、[0,4,7、 8]。現在の数値を挿入する反復の各ステップで、挿入した数値よりも大きいすべての数値の合計を知りたいです。したがって、上記の例では、次のようになります。
- [8]; 合計 = 0 挿入された数値 (8) より大きいすべての数値の合計は 0 であるため
- [4,8]; 合計 = 8 挿入された数値 (4) よりも大きいすべての数値の合計は 8 であるため
- [4,7,8]; 合計 = 8 挿入された数値 (7) よりも大きいすべての数値の合計は 8 であるため
- [0,4,7,8]; 合計 = 19 挿入された数値 (0) よりも大きいすべての数値の合計は 19 であるため
上記の例は単なる説明のためのものであり、元の配列ははるかに大きくなる可能性があるため、そのような合計を効率的に計算することが非常に重要になります。これを効率的に解決する方法について何か提案はありますか?
c++ - ダイナミック レンジ サム クエリ
CSESの問題を解決していました。これは単純なフェンウィック ツリーの問題であり、小さな入力に対しては完全に機能するが、大きな入力に対しては間違った答えを返すコードを書きます。問題のリンク: https://cses.fi/problemset/task/1648/問題 に対する私の解決策:
これは非常に簡単です。おそらく私は何を間違っていますか？