線分ツリーを使用した最長増加部分列 (LIS) の長さ

セグメント ツリーは、範囲クエリに応答し、対数的な時間計算量で配列更新操作を実行するように設計された多用途のデータ構造です。各ノードは配列内の特定の範囲で格納されます。要素。

最長増加部分列 (LIS) 問題のコンテキストでは、指定されたシーケンス内の要素が昇順に並べ替えられた最長部分列の長さを決定する必要があります。線分ツリーを使用すると効率的に計算できます。配列内で増加する最も長いサブシーケンスの長さ。

この方法は、従来の方法と比較して時間の複雑さを大幅に軽減し、ゲノミクス、自然言語処理、パターン認識などの分野で多くの用途があります。この記事では、セグメント ツリーの基礎を検討し、最長増加部分列問題を解決する際のセグメント ツリーの可能性を示します。

＃＃＃文法＃＃＃

セグメントツリー構築関数 −

リーリー

セグメントツリークエリ関数 −

リーリー

セグメントツリー更新機能 −

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

線分ツリーを使用して最長増加部分列 (LIS) の長さを求めるアルゴリズムは次のとおりです -

入力シーケンスを表す配列を初期化します。

入力シーケンスと同じサイズのセグメント ツリーで初期化します。 build 関数を使用して線分ツリーを構築する

• 入力シーケンスの各要素を処理します。

• 各要素について、セグメント ツリーをクエリして、現在の要素で終わる LIS の最大長を見つけます。

• 更新機能を使用してセグメント ツリーを更新します。

• 入力シーケンス内のすべての要素に対して手順 4 ～ 6 を繰り返します。

• 最終的な答えは、セグメント ツリーに保存されている最大値です。

• アプローチ 1: 単純なセグメント ツリーの使用

このアプローチでは、遅延伝播などの最適化手法を使用せずに単純なセグメント ツリーを実装します。

例-1

以下のプログラムは、C の単純なセグメント ツリーを使用して最長増加サブシーケンス (LIS) の長さを見つける方法を示しています。ビルド、クエリ、および更新関数を使用してセグメント ツリーを構築し、LIS 終了の最大長を取得します。特定の要素でセグメント ツリーを更新し、それぞれ新しい LIS 長でセグメント ツリーを更新します。lengthOfLIS 関数は、入力シーケンス内の各要素を反復処理し、セグメント ツリーを使用して LIS 長を計算します。

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

遅延伝播のあるセグメントツリーを使用する方法

このアプローチでは、遅延伝播を備えたセグメント ツリーを実装して、アルゴリズムの時間計算量をさらに最適化します。

例 2

次のコードは、遅延伝播のあるセグメント ツリーを使用して C で最長増加サブシーケンス (LIS) の長さを見つける方法を示しています。このコードはメソッド 1 のコードに似ていますが、2 つのメソッドの主な違いはセグメント ツリーの内部実装です。遅延伝播手法は、LIS 問題には存在しない特定の使用例に合わせて更新関数を最適化するため、このコードでは明示的に示されていません。ただし、コードの基本構造は同じであり、ビルド、クエリ、および更新関数は方法 1 と同様の方法で使用されます。

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

この記事では、C の線分ツリー技術を使用して最長増加部分列 (LIS) の範囲を決定する方法を説明します。ここでは 2 つのアプローチを説明します。1 つはセグメント ツリーを直接実行する方法、もう 1 つは遅延伝播の改良された方法を利用する方法です。どちらの手法も LIS 問題を解決するのに効果的であり、最適化手法における遅延伝播により時間の複雑さがさらに軽減されます。

以上が線分ツリーを使用した最長増加部分列 (LIS) の長さの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。