プレフィックスとツリー配列の配列更新を使用して、K の下限をクエリします。-C++-php.cn

プレフィックスとツリー配列の配列更新を使用して、K の下限をクエリします。

王林

リリース： 2023-09-04 17:33:04

転載

1370 人が閲覧しました

プレフィックスとツリー配列の配列更新を使用して、K の下限をクエリします。

プライマリシーケンス合計配列は、特定のインデックスに達するまでインターリーブされた要素の合計を蓄積するコレクションです。これは、時間の複雑さを最適化するために組み合わせリファクタリングで広く使用されている戦略です。バイナリインデックスツリー (BIT) とも呼ばれるツリー配列は、要素を効率的に更新し、対数時間計算量で以前のシーケンスの合計を計算するデータベース形式です。

この記事では、C でのフェンウィックツリーの最新の改良を使用して、系列合計配列から K と呼ばれる特定の値の小さい限界を明らかにする方法について説明します。

＃＃＃文法＃＃＃

この構文は、更新とクエリの 2 つの関数と、効率的な範囲クエリと更新操作に使用されるデータ構造であるフェンウィックツリーのメイン関数を定義します。 update 関数は、インデックス idx、値 val、配列のサイズ n、およびフェンウィックツリー配列 BIT を受け入れます。インデックス idx のノードとそのすべての先祖に val を追加することで、フェンウィックツリーを更新します。クエリ関数はインデックス idx とフェンウィックツリー配列 BIT を受け入れます。ルートノードからインデックス idx のノードまでの累積合計を返します。 main 関数は、配列のサイズ n、プレフィックスと配列 arr、および 0 に初期化されたフェンウィックツリー配列 BIT を宣言します。

リーリー＃＃＃アルゴリズム＃＃＃

フェンウィックツリーの更新を使用してプレフィックスと配列の K の最小値を決定するには、次の複雑な手順に従います -

サイズ n 1 のフェンウィックツリー (BIT) をインスタンス化し、すべての要素を 0 に初期化します。

update() 関数を使用して、指定されたプレフィックスと配列でフェンウィックツリーを変更します。
フェンウィックツリーに対してクエリを実行して、K の下限を決定します。 n のバイナリ表現の最上位ビットから最下位ビットまでを繰り返します。 query() 関数を使用して、現在のプレフィックスの合計が K 以下であるかどうかを確認します。この条件が満たされる場合、現在のプレフィックスの合計が K から減算され、インデックスが更新されて次のビットに移動します。条件が満たされない場合は、インデックスを更新せずに次のビットに移動します。
すべてのビットが走査された後、インデックスは配列内のプレフィックスと K の下限を表します。
取得したインデックスを K の下限として出力します。
＃＃＃方法＃＃＃

方法 1

-フェンウィックツリーで二分検索を実行します。この方法では、フェンウィックツリーで二分探索を実行して、K の下限を見つけます。

方法 2 - フェンウィックツリーでの遅延伝播による二分探索。
方法1 この問題を解決するには、まず左ポインタと右ポインタをそれぞれ 1 と n (プレフィックスと配列のサイズを示す) に設定し、次に二分探索戦略を使用して、最大のプレフィックス合計に対応するインデックスを決定します。 K i 以上。そして、プレフィックスsum[i]の値がK以下であるかどうかに応じて、左ポインタまたは右ポインタの位置が更新される。
＃＃＃例＃＃＃

findLowerBound 関数は、バイナリ検索アルゴリズムを使用して、関数にクエリを実行することで、プレフィックスと配列内の "k" の下限を見つけます。この関数は、フェンウィックツリーの現在のインデックスまでの値の累積合計を計算します。最終的に、コードは配列内の「k」の下限のプレフィックスとインデックスを特定し、結果をコンソールに表示します。

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

方法 2

フェンウィックツリーをさらに最適化するには、遅延伝播と呼ばれる手法を使用できます。このアプローチでは、実際に必要になるまでフェンウィックツリーへの更新を延期することになるため、更新の数が減り、クエリプロセスがより効率的になります。

＃＃＃例＃＃＃

このコードは、プレフィックス合計配列内の特定の値 K の下限を見つけるためのソリューションを提供します。プレフィックス合計配列は、各要素が元の配列のインデックス 0 からそのインデックスまでの要素の合計である配列です。下限は、そのインデックスまでの要素の合計が K 以上となる、プレフィックス合計配列内の最初のインデックスです。このソリューションでは、フェンウィックツリーデータ構造と遅延伝播技術を使用して、ソリューションの効率を高めます。このコードには、フェンウィックツリーの変更、プレフィックスの合計の計算、および下限の検索を行う関数が含まれています。このコードは、プレフィックス合計配列、フェンウィックツリー、および遅延伝播配列も初期化します。最後に、配列内のプレフィックスと K の下限を出力します。

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

慎重に設計されたプレフィックスと配列からとらえどころのない K 値のしきい値をマイニングすることについての説明。C プログラミングの世界の賢いフェンウィックツリーアルゴリズムを利用するアップデートによって強化されています。フェンウィックツリーでの二分探索と遅延伝播によるフェンウィックツリーでの二分探索という 2 つの効率的な方法の複雑さを詳しく見てみましょう。特定の問題の特定の要件と制約に基づいて、最も適切な方法を慎重に選択してください。これにより、C ドメインのフェンウィックツリーの比類のないパワーを活用して、更新を伴うプレフィックス合計の配列から K の下限を見つけるというとらえどころのないタスクの概念化と実装が明らかになることを願っています。

以上がプレフィックスとツリー配列の配列更新を使用して、K の下限をクエリします。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。