ツリー配列 (オフライン クエリ) を使用して、L から R の範囲内で K より大きい要素の数を計算します。

コンピュータ サイエンスの分野では、クエリの選択操作や更新操作を含む大規模なデータ セットを扱う必要があります。これらの操作を時間の複雑さを抑えてリアルタイムで実行することは、開発者にとって困難な作業です。

フェンウィック ツリーの使用は、これらの範囲ベースのクエリの問題を解決する効果的な方法です。

フェンウィック ツリーは、要素を効率的に更新し、テーブル内の数値のプレフィックスの合計を計算できるデータ構造です。バイナリ インデックス ツリーとも呼ばれます。

この記事では、フェンウィック ツリーを使用して L から R の範囲内で K より大きい要素の数を見つける方法について説明します。

入力シナリオと出力シナリオ

N 個の要素を含む配列があり、L から R の範囲内で K より大きい配列内の要素の数を見つけたいとします。

リーリー

オフライン クエリとは何ですか?

オフライン クエリは、所定のデータ セットに対して実行されるクエリ操作です。つまり、これらの操作は、クエリの処理中にさらに変更されないデータセットに対してのみ実行されます。

フェンウィック ツリーを使用する

ここでは、配列のすべての要素を順番に含むベクトルを各ノードに持つフェンウィック ツリーを使用します。次に、二分探索を使用して各クエリに答え、要素の数を数えます。

• BIT のプレフィックス合計を更新および取得するための 2 つの関数、updateTree() と total() をそれぞれ作成します。

• 次に、L から R の範囲で "K" より大きい要素をカウントする別の関数を作成します。この関数は、入力値 "arr"、"N"、"L"、"R"、および "K「」。

• カウントは、最大範囲 N の累積和から K の累積和を減算することによって計算されます。

範囲外の要素を除外するには、L-1 の累積和を減算します (L が 1 より大きい場合)。

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

代替方法

ここでは、クエリを保存するための別のベクトルを作成します。各クエリは、

index

と

val

という 2 つの変数で構成されます。 index は配列内の位置を格納するために使用され、val はそのインデックスの要素の値を格納するために使用されます。このアプローチにより、開発者はさまざまなクエリ操作を実行できるようになります。さらに、BIT を使用して、クエリごとに K を超える要素の数をカウントします。 ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃ インデックス L から R まで配列を単純に反復し、配列要素が K より大きくなるたびに 1 ずつインクリメントして、各クエリに対する答えを見つけることができます。ただし、時間の複雑さを軽減するために、Fenwick Tree を使用してこのようなクエリ操作を実行します。フェンウィック ツリーの代わりに

Line Segment Tree

と

Sparse Table

を使用して、このようなクエリ操作を実行することもできます。

以上がツリー配列 (オフライン クエリ) を使用して、L から R の範囲内で K より大きい要素の数を計算します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。