問題タブ [fenwick-tree]

最初に、「バランスの取れた」括弧の文字列を、すべての「(」に対して、その「(」の後のどこかに一意の一致する「)」が 1 つあるような文字列として定義します。

たとえば、次の文字列はすべて「バランス」です。

()

()()

(())()

これらはそうではありませんが：

)(

())(

括弧の文字列 (長さ <= 1,000,000) と範囲クエリのリストが与えられた場合、<= 100,000 の各クエリの各範囲内でバランスの取れた括弧の最大長を見つけます (範囲に 0 インデックスを使用)

元：

()))()(())

範囲: [0,3] -> 最長 = 2 : "()"

範囲: [0, 4] -> 最長 = 2 : "()"

範囲: [5, 9] -> 最長 = 4: "(())"

私の考えは次のとおりです。

まず、スタックを維持することで、文字列が「バランスが取れている」かどうかを判断できます。「(」に遭遇した場合はスタックにプッシュし、「)」に遭遇した場合はスタックからポップアウトします。末尾に「(」が残っている場合、文字列は「バランスが取れていません」。

ただし、すべての範囲でこれを繰り返すのは O(N*M) の複雑さであり、入力のサイズに対して長すぎます。

ここで、範囲クエリに注目すると、プレフィックスの合計とバイナリ インデックス ツリー/セグメント ツリーが思い浮かびます。プレフィックスの合計範囲全体を配列に事前計算できる場合は、差をとることで、より小さなプレフィックスの合計を見つけることができます。これにより、大きな複雑さが得られます。

+1 の値を '(' に、-1 の値を ')' に割り当てて、'(' に遭遇するたびに累積合計に 1 を追加し、') に遭遇したときにその方法を考えました。 'あなたは減少します。したがって、次のような有効な「バランスのとれた」文字列の))()場合: -1 -2 -1 -2.

しかし、私の質問は、これをどのように使用して「バランスが取れている」かどうかを判断するのですか? また、特定の間隔内で最大の「バランスの取れた」文字列を見つける必要があるため、特定の部分文字列が「バランスが取れている」かどうかを確認する機能を使用して、その特定の間隔内で最大の文字列を見つけるにはどうすればよいでしょうか。

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

長さ 3 の増加するサブシーケンスは、1,2,4 および 1,3,4 (インデックス ベース) です。

というわけで、答えは 2 です。問題 LINK

ソリューションを改善できる BIT ツリーを使用したより良いソリューションが必要です。BIT ツリーを使用してみましたが、時間制限を超えたというエラーが表示されます。

これがBIT実装コードです。

私も直接アプローチを試みました

私を助けてください

コマンド 's' を取得して範囲の合計を取得し、コマンド 'u' で要素を更新するプログラムを作成しましたが、正しく動作しません。お願い助けて。

正しい作業:

出力：

新しい古い値と新しい値の間のデルタを計算し、フェンウィック ツリーを更新しますが、うまくいきません。

これが私が解決したい問題です。私はThe Fact That Prefix Sum[i] - Prefix Sum[i-1]リードを使用してゼロよりも大きい周波数を使用して個別の数字を識別し、次に周波数を排除していますが、BITを使用してもTLEを取得しています

n 個の数値 a1、a2、...、an および多数の d クエリのシーケンスが与えられます。

d-query はペア (i, j) (1 ≤ i ≤ j ≤ n) です。

各 d クエリ (i、j) について、サブシーケンス ai、ai+1、...、aj 内の個別の要素の数を返す必要があります。

コードは次のとおりです。

配列 (ソートされていない) といくつかの範囲クエリが与えられます。クエリごとに、指定された範囲内の一意の桁数を見つける必要があります。これが私が思いついた素朴なアプローチです。

この操作を行う最も効率的な方法は何ですか? これは Binary Indexed ツリーを使用して実行できると思いますが、解決策を思い付くことができませんでした。

Java で非固定サイズのFenwick ツリーを実装する予定です。つまり、要素の追加/削除による範囲クエリのインターリーブを可能にする Fenwick ツリーです。

これまでに見たすべての実装とサンプルは、固定サイズの Fenwick ツリー用であり、周波数を前処理する前に要素の数がわかっています。固定サイズの配列を使用するため、前処理が完了した後に要素を追加または削除することはできません。（まあ、可能ですが、構造を再構築する必要があります）。

拡張するTreeMapか、おそらくを考えAbstractMapましたが、TreeMap実際には赤黒ツリーであるため、再調整プロセスに関与するノードの累積合計を失うことなく、赤黒メカニズムを実装する方法がわかりません (ツリーのバランスが保たれるようにするため)。 .

だから私はおそらく別のアプローチを取る必要があると思いました.単純なランダムアクセスを拡張または適応しArrayList、基になる配列のサイズが変更されたときにすべての累積合計を再計算してみませんか? これはもちろん影響がありますが、まさにそれが a のHashMap機能です。

これが、誰かがすでにそれを行っている場合に備えて、最初にここで質問し、どのアプローチが最善だと思うかを確認したかった理由です.