問題タブ [binary-indexed-tree]

編集: 私は spoj 問題を解決しようとしていました。問題へのリンクは次のとおりです。 http://spoj.pl/problems/BRCKTS

問題を解決するための 2 つの可能なデータ構造を考えることができます。1 つはセグメント ツリーを使用し、もう 1 つは BIT を使用します。セグメント ツリーを使用してソリューションを既に実装しています。BIT について読んだことがありますが、それを使って特定のことを行う方法がわかりません (以下で説明します)。

(のみまたはのみを含む特定の文字列で括弧のバランスが取れているかどうかを確認しようとしています)。問題を解決するためにBIT（バイナリインデックスツリー）を使用しています。私が従う手順は次のとおりです。

文字列の文字数と同じサイズの配列を取得しています。対応する配列要素に-1 for)と 1 forを割り当てています。(

次の 2 つの条件が true の場合にのみ、ブラケットは文字列内でバランスが取れています。

• 配列全体の累積合計はゼロです。
• 最小累積合計は負ではありません。つまり、配列のすべてのプレフィックスの累積合計の最小値は負ではありません。

BIT を使用して条件 1 をチェックするのは簡単です。条件2のチェックで問題に直面しています。

バイナリ インデックス ツリー (BIT) を使用して、特定の長さの増加するサブシーケンスの総数を見つけるにはどうすればよいですか?

実はこれはSpoj Online Judgeからの問題です

例
配列があるとします1,2,2,10

長さ 3 の増加するサブシーケンスは1,2,4、1,3,4

したがって、答えは2です。

A[k]範囲内の各要素がどこにある定数 [i..j]に更新されるように、範囲更新にバイナリ インデックス ツリーを使用するにはどうすればよいですか。A[k]*cc

そして、そのような更新操作の後にポイント クエリを実行する必要があります。

以下の関数を試してみましたが、うまくいきませんでした。n配列のサイズはc、範囲の各要素に掛けたい定数です。

これらは範囲を更新するための私の呼び出しです:

どんな種類の助けもいただければ幸いです。:)

ここに問題があり、ここに解決策があります。

最初の部分は簡単です。どんなに頑張っても手に入らない第二部です。基本的に 2 つの間隔のセットがあり、1 つの間隔が別の間隔内に完全に収まっていない交差点をすべて見つける必要があります。

目が充血するまで問題設定コードを見つめていました。まだこのビットを理解できません:

それはどのように機能しますか？アルゴリズムは何ですか？

社説には、インターバルツリーまたは「バイナリインデックスツリー」を使用してこれを解決できることが記載されています。間隔ツリーとは何か、またどのように役立つかについては、多かれ少なかれ理解しています。しかし、プロブレム セッターは明らかにそれを使用しておらず、「バイナリ インデックス ツリー」は検索に表示されません。関連性があることは確かですが、その方法がわかりません）。

何か助けはありますか？読む必要のある文献へのポインタはありますか?

配列 arr[0 があります。. . n-1]。0 <= qs <= qe <= n-1 のインデックス qs (クエリ開始) から qe (クエリ終了) までの最小値を効率的に見つけることができるはずです。

structure Segmentこのためのデータツリーを知っています。Binary Index Tree (BIT)この操作にも使用できるかどうか疑問に思っています。

はいの場合BIT、このシナリオでどのように使用できますか、配列は静的ですか、要素を変更して BIT またはセグメント ツリーを更新できますか。

範囲更新を行うときに、バイナリインデックスツリーで理解するのを手伝ってくれる人がいますか-すべての要素を更新しないのはなぜですか?開始要素と終了要素のみを更新するのはなぜですか?

たとえば 0

arr[x] の BIT の配列要素範囲を arr[y] に更新する必要があります。バイナリ インデックス ツリー ポイント更新関数に従って、インデックス x の累積頻度と、更新によって影響を受ける x よりも大きいすべてのインデックスを更新します。 .

しかし、範囲の更新にポイント更新関数を使用している場合は、ポイント更新関数を使用して x よりも大きく y よりも小さいすべてのインデックスを更新しない理由よりも。範囲更新はすべての要素を値で更新する必要があることを意味するため、開始インデックスと終了インデックスの上の 1 つを更新するとすべての更新がどのようにカバーされるか

なぜ私たちはしていないのですか

...................................................................

私

これは、インデックス 0 からインデックス X までの合計クエリのコードです。

2 つの配列がありますBIT[] and a[]。クエリ用に配列 a から BIT に値を格納します。ループに従って、インデックス X に値を追加し、最後に設定されたビットを削除してインデックスを変更します。

たとえば、 query(14) を呼び出すと、次のように実行されます。

合計 = ビット [14] + ビット [12] + ビット [8]

インデックス 8 の後に 8 のまま停止し1000、最後のビットを削除すると 0 になり、ループが終了します。つまり、インデックス 141110の場合、つまり、配列に 3 回アクセスすることを意味します。つまり、セットされたビットの数です。しかし、長いビットをチェックしました。たとえば、1000110111011101100セットビットは 11 ですが、答えは 12 で失敗しました。インデックス I のバイナリ値を確認することで、合計クエリの実行中に配列にアクセスした回数を知る他の方法はありますか?

私はそれを理解することはできません。私は多くのケースを試しましたが、1 少ない場合もあれば、1 多い場合もあれば、実際の答えである場合もあります。

私を助けてください。