更新操作を使用して、文字列内の範囲内で K 番目に大きい文字をクエリします。

フェンウィック ツリーは、O(log n) の時間計算量で範囲更新と範囲検索を実行できるデータ構造であり、バイナリ インデックス ツリー (BIT) とも呼ばれます

基本的な概念は、文字列内の各文字の頻度配列を保持し、i 番目の文字の頻度が頻度配列のインデックス i に記録されることです。周波数配列では、フェンウィック ツリーを使用した範囲の更新と範囲のクエリが可能になります。

問題の処理

次のクエリを使用すると、文字列から K 番目に大きい文字を抽出できます。更新範囲は [L, R] -

です。

• セグメント ツリーの構築 - まず、文字列内の各文字の頻度を格納するセグメント ツリーを作成します。セグメント ツリーの各ノードには、文字列内のインデックスの範囲を表す、範囲内の各文字の頻度を含む頻度配列が格納されます。

• Update - 前の文字の頻度を減らし、新しい文字の頻度を増やすことで、セグメント ツリー内の一致するリーフ ノードを更新することで、文字列内の文字を更新できます。

  李>

• K 番目に大きい文字の検索 - セグメント ツリーのルートから開始して、インデックスの関連範囲 [L, R] に再帰的に移動して、その範囲内で K 番目に大きい文字を検索します。範囲内で K 番目に大きい文字は、修正された二分探索を使用して各ノードで見つけることができます。

• 時間計算量 - は O (log n) です。n は文字列の長さです。セグメント ツリーの空間複雑さは O(n) です。

＃＃＃文法＃＃＃

文字列が最初に与えられ、更新できると仮定すると、クエリは文字列の区間 [L, R] 内で k 番目に大きい文字を見つけることです。次の構文を使用できます -

1.初期化文字列 -

リーリー

2. インデックス -

の文字列を更新します。 リーリー

3. 区間 [P, T] -

内で k 番目に大きい文字を検索します。 リーリー ＃＃＃アルゴリズム＃＃＃

指定された間隔 [L, R] から K 番目に大きい文字を見つけて更新するアルゴリズム -

ステップ 1

- サイズ 26 の配列 A を初期化します。ここで、各要素 A[i] は、文字列内の i 番目の文字 (0 からインデックス付け) の数を表します。

• ステップ 2
- 文字列 S を左から右にトラバースし、配列 A 内の各文字の数を更新します。

• ステップ 3
- 更新を処理するには、A と同じサイズの別の配列 B を保持し、ゼロに初期化します。

• ステップ 4
- 更新操作が実行されるたびに、古い文字数と新しい文字数の差を B の対応する要素に追加します。

• ステップ 5
- 区間 [L, R] 内で K 番目に大きい文字を見つけるには、インデックス R までの A と B の累積和を計算し、A の累積和を減算します。およびB、インデックスL-1まで。これにより、更新を適用した後の範囲 [L, R] 内の各文字の数が得られます。

• ステップ 6
- [L, R] の範囲内の文字をカウントの降順に並べ替えます。

• ステップ 7
- ソートされた順序で K 番目の文字を返します。

• 従うべき方法

方法1

この例では、文字列「abacaba」が初期文字列として使用されます。コンストラクター関数は、文字列内の各文字の出現をカウントすることによってセグメント ツリーを初期化します。 update 関数は、最初に古い文字の数を減らし、次に新しい文字の数を増やすことによって、文字列ツリーとセグメント ツリーを更新します。クエリ関数は二分検索を使用して、[L,R] 内の k 番目に大きい文字を返します。

例 1

リーリー ＃＃＃出力＃＃＃ リーリー

方法 2

プログラムはまず、サイズ N x 26 の 2 次元配列 freq を初期化します。ここで、freq[i][j] は、文字列 s のプレフィックス内の j 番目の文字から i 番目のインデックスまでの頻度を表します。次に、インデックス i ごとに、i 番目のインデックスの文字数をインクリメントし、以前のすべての文字のカウントを加算することによって、freq 配列を更新します。

freq 配列を初期化した後、2 つのクエリを実行します。各クエリでは、インデックス R の文字数からインデックス L-1 より前の文字数を減算して、範囲 [L, R] の文字数を計算します。次に、文字頻度を 0 から 25 まで繰り返し、これまでに表示された文字数を追跡します。 K 番目に大きい文字に到達すると、そのインデックスを保存し、ループから抜け出します。最後に、保存されたインデックスに対応する文字を出力します。

2 つのクエリの間で、インデックス 4 の文字を「a」に変更して文字列を更新します。 freq 配列を効率的に更新するには、対応するインデックスで古い文字と新しい文字の数を更新し、更新されたプレフィックスの合計を使用して後続のすべての文字の数を再計算します。

例 1

リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃

最後に、更新を含む区間 [L, R] 内で K 番目に大きい文字を識別するという要求は、線分ツリーと二分探索法の組み合わせを使用して効果的に解決できます。二分探索手法は範囲内で K 番目に大きい文字を見つけるために使用され、線分ツリーは範囲内での文字の出現頻度を追跡するために使用されます。

以上が更新操作を使用して、文字列内の範囲内で K 番目に大きい文字をクエリします。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。