問題タブ [fenwick-tree]

http://ayazdzulfikar.blogspot.in/2014/12/penggunaan-fenwick-tree-bit.html?showComment=1434865697025#c5391178275473818224

たとえば、関数の値またはインデックス i の f (i) は i ^ k であると言われ、k> = 0 の場合、常にこの問題にとどまります。次のようなクエリを指定します。

すべての a <= i <= b に対して、値配列 [i] を v として追加します。 a <= i <= b ごとに、合計配列 [i] f (i) を決定します (前の関数値の説明を思い出してください)。

これを達成するには、m と c の値を知る必要があります。そのためには、2 つの個別の BIT が必要です。ab v の形式での各更新に関する以下の観察。m の値を計算するには、Range Update - Point Query と実質的に同じです。i の各値について、次の観測結果を得ることができます。

次の観察を使用することにより、Range Update - Point Query を任意の BIT で使用できることは明らかです。c の値を計算するには、i の各値の可能性を観察する必要があります。

ここでも、Range Update - Point Query が必要ですが、BIT が異なります。大谷、ちょっとした助けとして、k <= 3 の場合の g (x) の値を書きました はい: p:

さて、問題の例 SPOJ - Horrible Queries 。この問題は、k = 0 で説明した問題と似ています。また、関数が 1 つのタイプの k ではなく、その多項式の形状である可能性があるという、非常に極端な問題があることにも注意してください。例：LA - エイリアン・アブダクション・アゲイン。この問題を解決するには、ランクごとに BIT カウンターをそれぞれ m にします。BIT を組み合わせてカウンターをクリアしました c 問題ありませんでした。

次の場合、この概念をどのように使用できますか。

整数の配列 A1、A2、…AN が与えられます。

与えられた x,y: Ax に 1×2 を足し、Ax+1 に 2×3 を足し、Ax+2 に 3×4 を足し、Ax+3 に 4×5 を足し、というように Ay まで続けます。

次に、範囲 [Ax,Ay] の合計を返します。

問題文：

https://www.hackerrank.com/contests/epiccode/challenges/square-array

整数 A1、A2、…AN の配列が与えられた場合、配列内で 2 種類のクエリを実行する必要があります。

• 1×y。Ax に 1×2 を追加し、Ax+1 に 2×3 を追加し、Ax+2 に 3×4 を追加し、Ax+3 に 4×5 を追加します。

• 2×y。インデックス x からインデックス y までのすべての整数の合計を 109+7 で法を求めて求めます。つまり、(Ax+Ax+1+⋯+Ay)mod(109+7) を求めます。

最初は配列内のすべての値が 0 であると想定できます。

入力フォーマット:

最初の行には、スペースで区切られた 2 つの整数 N と Q が含まれています。N は配列のサイズを表し、Q はクエリの数を表します。

次の各 Q 行には、1 xy または 2 x y の形式のクエリが含まれます。

制約:

1≦x≦y≦N 1≦N≦2×10^5 1≦Q≦2×10^5

出力形式 フォーム 2 xy のクエリごとに、必要な回答を出力します。

説明：

提出された解決策の1つ:

フェンウィック ツリーは、主なクエリに答える効率的な方法を提供するデータ構造です。

• 配列の特定のインデックスに要素を追加するupdate(index, value)
• 1 から N までの要素の和を求めるfind(n)

両方の操作は時間内に完了し、ロジックと実装O(log(n))を理解しています。N から M の合計を求めるなど、他の多くの演算を実装するのは難しくありません。

フェンウィック ツリーを RMQ に適応させる方法を理解したかったのです。最初の 2 つの操作でフェンウィック ツリーを変更することは明らかです。しかし、N から M までの範囲で最小値を見つける方法がわかりません。

解決策を探した後、大多数の人はこれは不可能だと考えており、実際にはできると主張する少数派もいます (アプローチ1 、アプローチ2 )。

最初のアプローチ (ロシア語で書かれており、Google 翻訳には説明がなく、関数は 2 つしかないことに基づいています) は、考えられるすべてのテスト ケースでテストが正しく機能しなかったため、3 つの配列 (初期、左、右) に依存しています。

2 番目のアプローチでは、必要なアレイは 1 つだけであり、要求に基づいて実行されO(log^2(n))ますが、それが機能する理由と方法についての説明もほとんどありません。私はそれをテストしようとはしていません。

update(index, value)物議を醸す主張に照らして、フェンウィック木を拡張してとを答えられるかどうかを調べたかったのfindMin(from, to)です。

可能であれば、その仕組みをお聞かせいただければ幸いです。

単純な方法は、範囲を線形に反復し、範囲内の各数値を乗算することです。

例: 配列: {1,2,3,4,5,6,7,8,9,10}; インデックス 3 からインデックス 8 を 2 で乗算します。1 ベースのインデックスを想定しています。

結果配列は次のようになります: {1,2,6,8,10,12,14,16,9,10};

「合計」部分にバイナリ インデックス ツリーを使用できることはわかっています。特定の範囲を数値で効率的に乗算するにはどうすればよいですか?

フェンウィック ツリーでは、値の加算や値の乗算などの更新を行うことができます。位置 l の要素に値 x を追加する次のコードがあります。

同様に、乗算演算を実行したいのですが、その方法がわかりません。どんな助けもかなりのものです。

条件付きで BIT の範囲更新を実行できますか。負と正の周波数 A[] = {1, -3, -4, 5, 9} の配列があるとします。そして、条件を使用して配列の値を範囲更新したかった：更新値（x）が負の場合は負の要素のみを更新し、更新値が正の場合は範囲​​内の正の値のみを更新します。

たとえば、上記の配列で、更新クエリが 2 4 -2 (左右の値) の場合、2 番目 (-3) と 3 番目 (-4) の位置のみを更新します。正の整数であるため、4th(5) の位置を残します。

または、これを達成するために別のデータ構造を使用する必要がありますか?

これを使用して、範囲の更新を学習しました。

フェンウィック ツリー アルゴリズムの次の実装があります。

N<=5000000このプログラムは、 を実行して処理できる必要がありますQ<=5000000。そして、それは9秒未満で実行できるはずです。しかし、この問題を提出した後、Time Limit Exceeded (TLE) の評決が下されました。このコードを最適化するためにあらゆる手段を試しましたが、役に立ちませんでした。それでも TLE が発生しました。このコードを最適化して、9 秒未満で実行できるようにするにはどうすればよいでしょうか。どうもありがとうございました。

例えば：

ツリー更新機能:

を使用して、コードで何をするのか説明していただけます( (i) & (-i) )か?

問題のリンクはこちらです。問題は、基本的に、要素の合計が A と B の間である、サイズ N × M の特定の行列のそのようなすべての部分行列を数えることです。N、M<=250。10^-9<=A<=B<=10^9。

人々はDPとBITを使用してそれを解決しました。方法はわかりません。

最初に、上記の問題のより単純なバージョンである 1 次元のケースを解決しようとしました: 長さ N の配列 A が与えられた場合、サブ配列内の要素の合計が A と B の間にあるすべてのサブ配列を数えますが、それでもできませんでしたO（n ^ 2）よりも優れていると考えてください。これが私がしたことです：

元の配列のプレフィックス合計を保持するための別の配列を作成することを考えました。たとえば、prefix[N] です。プレフィックス[i] = A 1 + A[2] + A[3] + ...A[i]。プレフィックス [1] = A [1] を設定します。次に、2 から N までの各 i について、合計 Z = A[j] + A[j+1] + ..A[i] が A と B の間にあるように、すべての j <= i を数えます。これは等価です。接頭辞[i] - 接頭辞[j-1]。しかし、それはまだ O(n^2) です。各 i について、j は i か所にヒットしています。

主な問題を解決するために与えられたアプローチで私を前進させるために、誰かが私を一歩一歩助けてくれますか?.