fenwick-tree

0熱

1答えて

バイナリインデックスツリーで範囲の更新と範囲のクエリを実装するにはどうすればよいですか？

バイナリインデックス付きツリーでいくつかのチュートリアルを読んだことがありますが、クエリと更新の両方の操作がある範囲内にあるときに、その実装方法を理解できません。

0熱

1答えて

私はHackeEarthの次のような問題を解決するために、次のフェンウィックツリーの実装を行っています：Question #include <iostream> #define MAX 1000000007 using namespace std; long long int dp[500006]; long long int GCD[500006]; // Function t

0熱

1答えて

範囲lからrまでのすべてのインデックスiの最後のk項の合計を求める方法は？

フェンウィック・ツリーを使用してq個の問合せに対してn個のサイズの配列の範囲l〜rにあるすべての索引iの最後のk項の合計を見つける方法は問合せごとに異なります。ハッカーの問題ですhacker with team そのチュートリアルではありませんが、私は説明が与えられていないので、彼らがどのようにしたのか分かりません。それはどうやって説明できますか？

7熱

1答えて

バイナリインデックスツリー（BIT）で特定の長さのサブシーケンスを増やす方法の総数を確認する方法

バイナリインデックスツリー（BIT）を使用して特定の長さのサブシーケンスを増やす総数を調べるにはどうすればよいですか？は、実際にはこの例Spoj Online Judge から問題であると仮定私はアレイ1,2,2,10 長さ3である1,2,4ので 1,3,4、回答の増加サブシーケンス2です。

1熱

1答えて

ツリーを配列に線形化し、パス上の "sum"クエリに応答する

問題はコーデックのtravtree問題によって動機付けられます。 editorialでは、各ノードの検出と終了時間をDFSトラバーサルで記録することによって、ツリーを配列に線形化することを推奨しています。今すぐ、そのノードの[discovery time, exit time]セグメントで発生したイベントを合計することで、sum subtreeに関する質問に素早く答えることができます。（私たちは

2熱

2答えて

BITのプリフィックスサムMを持つ位置を見つける方法は？

長さNの接頭辞の合計を持つバイナリインデックスツリーを作成したとします。メイン配列には0と1が含まれています。今私はどのインデックスが接頭辞の合計Mを持っているかを見たいと思っています（つまり、正確にはM 1です）。私の配列のようにはa[]={1,0,0,1,1}; プレフィックス合計は{1,1,1,2,3}; 今第三インデックスiはBITでこのインデックスを見つけることができますどのように2