問題タブ [fenwick-tree]

この質問は、codechef のtravtree問題に動機付けられています。社説DFSでは、トラバーサルで各ノードの発見と終了時間を記録することにより、ツリーを配列に線形化することを推奨しています。これで、そのノードsum subtreeのセグメントで発生したイベントを合計することで、クエリにすばやく答えることができます。[discovery time, exit time](Fenwickこれらのクエリにすばやく答えるためにツリーを使用しています)。

ただし、その問題を解決するには、sum pathクエリにすばやく応答する必要もあります。つまり、 の間の最短経路に沿って発生したイベントを合計しますa, b。そんなことがあるものか？彼らが与える答えはこれです：

興味深いイベントごとに、これを更新します。

そしてsum path(a,b)今これです：

query接頭辞の合計はどこにありますか. それはどのように正しいですか?? aとの間のパスに関係のない多くのノードに遭遇する可能性があるまで、プレフィックスの合計を見るlとa!

HackeEarthに関する次の質問を解決するために、フェンウィック ツリーを次のように実装しています。

私のソリューションは、10 個のテスト ケースのうち 7 個の制限時間を超えています。このコードをさらに最適化することはできません。テストケースごとに1秒未満で実行できるように、これを最適化するにはどうすればよいでしょうか。どうもありがとうございました ！

次のように定義されている問題を解決しようとしています。

キャンディーは 1 から 1e6 までの数字で表されます。1 から k 個までのキャンディーを持っている人は、k 個のキャンディーを持っていると言われます。

たとえば、ある人がキャンディー 1、2、および 6 を購入した場合、その人はキャンディー 2 個のセットを持っています。

与えられた 2 種類の操作: x を食べる、x を買う、x はキャンディーの数を表します。x を購入すると、x の数量が 1 だけ増えます。x を食べると、x の量が 1 だけ減少します。

各操作について、質問に答えてください。私が今持っているキャンディーのセットのサイズはどれくらいですか?

これを行うための最も効率的な方法を見つけようとしています。私が考えた解決策は以下のとおりです。

count[i] でサイズ 1 ～ N の配列を定義します。ここで、N はキャンディーの最大数です。count[i] には、これまでに持っていた i 番のキャンディーの数が格納されます。

Fenwick[i] をサイズ 1 ～ N の配列とします。ここで、N はキャンディーの最大数です。この配列は、フェンウィック ツリーを構築して、コレクション内のキャンディーの累積合計を格納するためのものです。この累積合計は count 配列を使用しません。累積合計は、1 の数量をカウントします (各 1 は、キャンディー x が私のコレクションに存在することを示します)。たとえば、5 個のキャンディーのセットがある場合、1 から 5 までの累積合計は 5 です。10 個のキャンディーのセットがある場合、1 から 10 までの累積合計は 10 です...

購入操作の場合、キャンディー x がまだコレクションにない場合は、インデックス x から始まる累積合計に 1 を追加します (これはフェンウィック ツリーによって処理されます)。それ以外の場合は、count[x]++ を実行します

Eat 操作の場合、count[x]-- を実行します。count[x] が現在 0 の場合、インデックス x から始まる累積合計から 1 を減らします (これはフェンウィック ツリーによって処理されます)。

これで、挿入と削除の部分が決まりました。難しいのは、現在コレクションにあるキャンディーのセットのサイズを取得する方法です。

毎回 2 の累乗でクエリ インデックスをインクリメントしながら、1 から i までの累積合計が i に等しい最大のインデックス i をフェンウィック ツリーにクエリしようとしました。

キャンディーの有効なセットである最大のインデックス j と、キャンディーの無効なコレクションである最小のインデックス k を取ります。次に、j から k までループし、各反復でフェンウィック ツリーをクエリします。ループが無効なコレクションに到達したら、中断して回答を出力します。

これはうまくいくように思えます。ただし、これは確かに効率的な方法ではありません。より良い解決策を教えてくれる人はいますか? 前もって感謝します。

編集（解決策）：

挿入と削除に対する私のアプローチは正しかった。キャンディーのコレクションを間違った方法で探していたというだけです。この場合、最大数 x が必要です。ここで、query(x) = x (query(x) は 1 から x までの累積合計を返します)。したがって、二分探索を使用して x の有効な最大値 (query(x) = x) を見つけることができます。これを実現するには、追加の変数を保持して、query(x) が有効なコレクションを提供する x の最後の値を追跡する必要があります。

解の複雑さ: O(log^2(N))

指定された整数の配列について、指定されXORedた範囲内で合計[L, R]をXORed計算する必要Σ(Arr[i]^p)がi:[L,R]ありpます。これは、配列の先頭から配列内のXORedすべての要素までの合計を計算しながら簡単に実行できます。が非常に頻繁i-thに変更されると、問題が発生します。この場合、すべての要素がなくなるまで合計をp再計算することは理想的な解決策のようです。これはorを使用して実行できると思います。しかし、私はツリーまたはを続行する方法を理解できません。どんな助けでも大歓迎です。XORedi-thfenwick treeBITfenwickBIT

フェンウィックツリーを使用して文字列を範囲クエリしたい。しかし、私のコードで何か問題が発生しています。連結によりエラーが発生します Eror is:[Error] no match for 'operator+=' (operand types are 'std::vector >' and 'std::string {aka std::basic_string}') 文字列 s が与えられた場合、このフェンウィック ツリーに文字列を格納します。例: s=abcdef、BIT では、(上から下) ab-c abcd-e abcd-ef ツリー構造のようにする必要があります