1. 概要

このチュートリアルでは、ツリーデータ構造であるセグメントツリーメソッドについて説明します。 次に、いくつかの例を見ていきます。

2. セグメントツリー法の定義

セグメントツリーは、計算幾何学からのデータ構造の一種です。 Bentley は、1977年にこのよく知られた手法を提案しました。 セグメントツリーは基本的にバイナリツリーであり、そのノードには、配列などの線形データ構造のセグメントに関する情報が格納されます。

さらに、更新とともに範囲クエリに関する質問を解決するのに役立ちます。 このメソッドは、対数時間で間隔または範囲クエリを実行できるようにし、そのようなクエリを多数処理する必要がある場合に利用できます。

このメソッドを動的構造にすることも可能です。

3. 例を使用してセグメントツリーメソッドを理解する

セグメントツリーを使用して、範囲の最小/最大および合計クエリと範囲更新クエリをO（log n）時間で解決できます。 これらの問題は、セグメントツリー手法を使用して簡単に解決できます。 このような問題を効率的に解決することで、この方法を学ぶことができます。 基本的に、セグメントツリーには次の3つの操作しかありません。

  • ツリーの構築：このステップでは、セグメントツリー変数の構造を作成して初期化します。
  • ツリーの更新：このステップ中、あるポイントまたは間隔で配列の値を更新することにより、ツリーを変更します
  • クエリツリー：この操作を使用して、配列に対して範囲クエリを実行できます

セグメントツリーでは、配列はツリーのリーフに格納され、内部ノードはその子によって表されるセグメントに関する情報を格納します。 内部ノードは、子ノードからの情報をマージすることにより、ボトムアップ方式で形成されます。

セグメントツリーは、さまざまな数値データを頻繁に操作する場合に役立ちます。 このコンテキストでは、各ステップを説明することにより、セグメントツリーをよりよく理解するための例を見てみましょう。 配列内の要素の合計を見つけることができるセグメントツリー配列を構築したいと思います。

3.1. セグメントツリーの構築

ツリーを構築する最初のステップから始めましょう。

値[、、、、、、、]を持つ配列があり、範囲の合計を照会したいとします。 したがって、このシナリオでは、セグメントツリー内のすべてのノードがその子ノードの合計になります。

二分木であるため、ノードの配列表現の子ノードはとであることがわかります。 簡単にするために、とを含む配列全体を1つのインデックス付き配列として扱います。 その結果、セグメントツリーの各要素はになります。ここで、はノードのインデックスであり、リーフノードは配列の要素を表します。

以下は、与えられた配列に対して私たちが持っているツリーです：

配列はツリーの葉に表示されます。

次の図は、セグメントツリーがどのように更新されるかを説明しています。

3.2. セグメントツリーの値の更新 

配列要素を更新するには、セグメントツリーも更新する必要があります。 実際、セグメントツリー内の要素がその親要素にのみ寄与することを考えると、高さをトラバースするだけでよいため、値の変更は複雑に行われる可能性があります。

したがって、値を更新するには、要素の新しい値と現在の値の差であるdiffを簡単に決定できます。

ご覧のとおり、配列のthメンバーの値を更新するには、そのすべての親ノードを更新する必要があります。

次の図は、特定の範囲でクエリを実行するための作成方法を示しています。

3.3. 範囲クエリの作成

次に、次の配列と前のセクションのセグメントツリーを使用して範囲クエリを作成する方法を見てみましょう。

配列内の〜の範囲で合計クエリを実行するとします。 セグメントツリーも複雑さを使用できます。 toの範囲の合計クエリは次のように動作します。

のノードにはとの合計があり、はにあることがわかります。 したがって、次のように書くことができます。

走査は常に木の高さに依存するため、常にです。

次に、範囲の合計を見つけるためのさまざまなケースについて説明します。

のノードの合計は、などの特定の範囲で常に分割できます。

その結果、範囲の合計を計算する際に、次の3つのシナリオが予想されます。

  • のノードが、、、、、のように必要な合計を提供していない可能性があります。 したがって、そのセグメントツリーノードに格納されている値を取得するだけです。
  • のノードは、、のように、必要な合計の中に完全に含まれている可能性があります。 したがって、ノードの値を返します。これは、ノードが表す範囲内のすべての要素の合計です。
  • ノードは、、、、など、必要な合計の一部を提供する場合があります。 したがって、左の子と右の子の合計を返します。

4. セグメントツリーのアプリケーション

セグメントツリーは、意欲的なコンピュータサイエンスエンジニアだけでなく、趣味としてコーディングするすべての人にとって、レパートリーに含まれる重要なデータ構造です。さらに、セグメントツリーにはさまざまな可能性があります。アプリケーション。

さまざまな分野のいくつかのアプリケーションを見てみましょう。

  • 初期の頃は、セグメントツリーを使用して、平面内の長方形のリストから交差する長方形のすべてのペアを効率的にリストしていました。
  • このメソッドを使用して、クエリラインセグメントと交差する平面内のすべての直線ラインセグメントのリストをレポートできます。
  • この手法を使用して、平面内の一連の長方形の周囲長を報告します。
  • 最近では、セグメントツリーがパターン認識や画像処理での使用に人気があります。

非常によく知られている他のアプリケーションを指定することもできます。

  • 範囲の合計/製品、範囲の最大/最小、プレフィックスの合計/製品などを検索する
  • 計算幾何学
  • 地理情報システム
  • 静的および動的RMQ（範囲最小クエリ）
  • 任意の方法でセグメントを保存する

5. 結論

この記事では、セグメントツリーを作成し、値を更新し、範囲クエリベースの問題を効率的に解決するために使用できる範囲クエリを作成する方法を学習しました。 このタイプのデータ構造は有利であり、さまざまな分野で多くの用途があります。