プレフィックスとツリー配列の配列更新を使用して、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以下であるかどうかに応じて、左ポインタまたは右ポインタの位置が更新される。

  ＃＃＃例＃＃＃
このコードの基本的なメカニズムは、フェンウィック ツリー (バイナリ インデックス ツリーとも呼ばれる) と呼ばれるデータ構造を利用することです。その目的は、プレフィックス合計配列内の指定された値 'k' の下限を決定することです。これは、配列内の各要素のプレフィックスと値をフェンウィック ツリー内の対応する位置にマージする更新関数を使用してフェンウィック ツリーを構築することで実現されます。

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

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

方法 2

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

＃＃＃例＃＃＃

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

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

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

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