data-structures => セグメントツリー

セグメントツリーの概要

配列があるとします。

+-------+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |
+-------+-----+-----+-----+-----+-----+-----+
| Value |  -1 |  3  |  4  |  0  |  2  |  1  |
+-------+-----+-----+-----+-----+-----+-----+

この配列に対して何らかのクエリを実行する必要があります。例えば：

インデックス2からインデックス4までの最小値はいくらですか？ →0
インデックス0からインデックス3の最大値はいくらですか？ →4
インデックス1からインデックス5までの合計は何ですか？ →10

どうやってそれを見つけるのですか？

強引な：
配列を開始インデックスから終了インデックスまでトラバースし、クエリに答えることができます。このアプローチでは、各クエリはO(n)時間かかるが、ここでnは開始インデックスと終了インデックスの差である。しかし、数百万の数百万のクエリがある場合はどうなりますか？ m個の照会では、 O(mn)時間がかかります。したがって、配列内の105個の値に対して、最悪の場合、10 5個のクエリを実行すると、1010個のアイテムをトラバースする必要があります。

動的プログラミング：
さまざまな範囲の値を格納する6X6行列を作成できます。レンジ最小問合せ（RMQ）の場合、配列は次のようになります。

              0     1     2     3     4     5
     +-----+-----+-----+-----+-----+-----+-----+
     |     |  -1 |  3  |  4  |  0  |  2  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+
  0  |  -1 |  -1 |  -1 |  -1 |  -1 |  -1 |  -1 |
     +-----+-----+-----+-----+-----+-----+-----+
  1  |  3  |     |  3  |  3  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+
  2  |  4  |     |     |  4  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+
  3  |  0  |     |     |     |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+
  4  |  2  |     |     |     |     |  2  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+
  5  |  1  |     |     |     |     |     |  1  |
     +-----+-----+-----+-----+-----+-----+-----+

この行列を作成したら、すべてのRMQに答えるだけで十分です。ここで、 Matrix [i] [j]は、index -iからindex- jまでの最小値を格納します。例：インデックス2からインデックス4までの最小値は、 Matrix [2] [4] = 0です。この行列はO(1)時間のクエリに応答しますが、この行列を構築するためにはO(n²)それを格納するにはO（n²）の時間がかかります。だから、 nが本当に大きい数字なら、これはうまくスケールされません。

セグメントツリー：
セグメントツリーは、間隔またはセグメントを格納するためのツリーデータ構造です。これは、記憶されたセグメントのうちのどれが所与のポイントを含むかを照会することを可能にする。セグメントツリーを構築するのにO(n)時間がかかり、 O(n)スペースを維持してO(logn)時間でクエリに応答します。

セグメントツリーはバイナリツリーであり、与えられた配列の要素はそのツリーの葉になります。 1つの要素に到達するまで配列を半分に分割してセグメントツリーを作成します。私たちの部門は私たちに次のものを提供します：

今、葉以外のノードを葉の最小値に置き換えると、次のようになります。

これは私たちのセグメントツリーです。ルートノードには配列全体の最小値（範囲[0,5]）が含まれ、左の子には左辺配列の最小値（範囲[0,2]）が含まれ、右の子には最小値私たちの右の配列の値（範囲[3,5]）など。葉ノードは、個々の点の最小値を含む。我々が得る：

今度は、このツリーで範囲クエリを実行しましょう。範囲クエリを実行するには、次の3つの条件を確認する必要があります。

部分オーバーラップ：両方の葉をチェックします。
Total Overlap：ノードに格納されている値を返します。
オーバーラップなし：非常に大きな値または無限大を返します。

たとえば、範囲[2,4]を確認したいとしましょう。インデックス2から4までの最小値を求めたいということです。ルートから始め、ノード内の範囲がクエリの範囲と重なっているかどうかを確認します。ここに、

[2,4]は完全に[0,5]に重ならない。そこで、両方向をチェックします。
- 左のサブツリーで[2,4]は部分的に[0,2]と重なります。両方の方向を確認します。
  - 左のサブツリーで[2,4]は[0,1]と重ならないので、これは私たちの答えに寄与しません。私たちは無限を返す。
  - 右のサブツリーでは、 [2,4]は完全に[2,2]と重なっています。我々は4を返します。
    これらの2つの戻り値の最小値（4、無限大）は4です。私たちはこの部分から4を得る。
- 右のサブツリーで[2,4]は部分的に重なります。そこで、両方向をチェックします。
  - 左のサブツリーで[2,4]は完全に[3,4]と重なります。我々は0を返す。
  - 右のサブツリーで[2,4]は重ならない[5,5] 。私たちは無限を返す。
    これらの2つの戻り値の最小値（0、無限大）は0です。この部分から0が得られます。
戻り値の最小値（4,0）は0です。これは、範囲[2,4]における望ましい最小値である。

これで、クエリが何であっても、このセグメントツリーから目的の値を見つけるのに最大4ステップかかることが確認できます。

つかいます：

範囲最小クエリ
最も低い共通祖先
レイジー伝播
動的サブツリー合計
ネグレクト＆ミン
デュアルフィールド
k番目の最小要素を求める
順序付けられていないペアの数の検索

配列を用いたセグメントツリーの実装

たとえば、 Item = {-1, 0, 3, 6}という配列があるとします。与えられた範囲内の最小値を見つけるためにSegmentTree配列を構築したい。私たちのセグメントツリーは次のようになります：

ノードの下の数字は、 SegmentTree配列に格納する各値のインデックスを示しています。 4つの要素を格納するために、サイズ7の配列が必要であることがわかります。この値は、次のように決定されます。

Procedure DetermineArraySize(Item):
multiplier := 1
n := Item.size
while multiplier < n
    multiplier := multiplier * 2
end while
size := (2 * multiplier) - 1
Return size

したがって、長さ5の配列がある場合、 SegmentTree配列のサイズは（ 8 * 2 ） - 1 = 15になります。ここで、ノードの左と右の子の位置を決定するために、ノードがインデックスiにある場合、そのノードの位置は：

左の子は、（2 * i） + 1で表される。
右の子は、（2 * i） + 2で表される。

そして、インデックスiの任意のノードの親のインデックスは、（i - 1） / 2によって決定することができる。

したがって、例を表すSegmentTree配列は次のようになります。

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
|  -1 |  -1 |  3  |  -1 |  0  |  3  |  6  |
+-----+-----+-----+-----+-----+-----+-----+

この配列を作成する擬似コードを見てみましょう：

Procedure ConstructTree(Item, SegmentTree, low, high, position):
if low is equal to high
    SegmentTree[position] := Item[low]
else
    mid := (low+high)/2
    constructTree(Item, SegmentTree, low, mid, 2*position+1)
    constructTree(Item, SegmentTree, mid+1, high, 2*position+2)
    SegmentTree[position] := min(SegmentTree[2*position+1], SegmentTree[2*position+2])
end if

最初に、値の入力を受け取り 、 Item配列の長さをそのサイズとしてinfinityのSegmentTree配列を初期化します。このプロシージャは、次のものを使用して呼び出します。

低= アイテム配列の開始インデックス。
高= アイテム配列の仕上げインデックス。
position = 0は、セグメントツリーのルートを示します。

ここでは例を使って手順を理解してみましょう：

Item配列のサイズは4です。長さ（4 * 2） - 1 = 7の配列を作成し、 infinityそれらを初期化しinfinity 。あなたはそれに非常に大きな値を使うことができます。私たちの配列は次のようになります：

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf | inf | inf | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+

これは再帰的なプロシージャなので、コールごとにlow 、 high 、 position 、 midおよびcalling lineを追跡する再帰表を使用して、 ConstructTreeの操作を確認します。最初に、 ConstructTree（Item、SegmentTree、0、3、0 ）を呼び出します。ここでは、 low同じではありませんhigh 、我々が得るでしょうmid 。 calling lineは、この文の後にどのConstructTreeが呼び出されるかを示します。プロシージャ内のConstructTree呼び出しをそれぞれ1と2と示します。私たちのテーブルは次のようになります：

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+

ConstructTree-1を呼び出すと、 low = 0 、 high = mid = 1 、 position = 2*position+1 = 2*0+1 = 1渡されます。あなたが気付くことができることの1つは、 2*position+1はルートの左の子です。これは1です。 lowはhighと等しくないので、私たちはmidを得ます。私たちのテーブルは次のようになります：

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       1      |
+-----+------+----------+-----+--------------+

次の再帰呼び出しでは、 low = 0 、 high = mid = 0 、 position = 2*position+1 = 2*1+1=3を渡します。再度、インデックス1の左の子は3です。ここで、 lowはe highので、 SegmentTree[position] = SegmentTree[3] = Item[low] = Item[0] = -1ます。 SegmentTree配列は次のようになります：

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf |  -1 | inf | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+

私たちの再帰テーブルは次のようになります：

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   0  |     3    |     |              |
+-----+------+----------+-----+--------------+

それで、 -1が正しい位置にあることが分かります。この再帰呼び出しは完了しているので、再帰テーブルの前の行に戻ります。テーブル：

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       1      |
+-----+------+----------+-----+--------------+

ここでは、 ConstructTree-2呼び出しを実行します。今回は、 low = mid+1 = 1 、 high = 1 、 position = 2*position+2 = 2*1+2 = 4を渡します。私たちのcalling lineは2に変わります。我々が得る：

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       2      |
+-----+------+----------+-----+--------------+

以来lowに等しいhigh 、我々は設定： SegmentTree[position] = SegmentTree[4] = Item[low] = Item[1] = 2 。私たちのSegmentTree配列：

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf |  -1 |  2  | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+

私たちの再帰テーブル：

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       2      |
+-----+------+----------+-----+--------------+
|  1  |   1  |     4    |     |              |
+-----+------+----------+-----+--------------+

もう一度あなたは見ることができます、 2は正しい位置を持っています。この再帰呼び出しの後、再帰テーブルの前の行に戻ります。我々が得る：

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       2      |
+-----+------+----------+-----+--------------+

SegmentTree[position] = SegmentTree[1] = min(SegmentTree[2*position+1], SegmentTree[2*position+2]) = min(SegmentTree[3], SegmentTree[4]) = min(-1,2) = -1 。私たちのSegmentTree配列：

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
| inf |  -1 | inf |  -1 |  2  | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+

この再帰呼び出しが完了しているので、再帰テーブルの前の行に戻り、 ConstructTree-2を呼び出します。

+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       2      |
+-----+------+----------+-----+--------------+

セグメントツリーの左部分が完成していることがわかります。このようにして処理を続けると、最後にSegmentTree配列が完成します。

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
|  -1 |  -1 |  0  |  -1 |  2  |  4  |  0  |
+-----+-----+-----+-----+-----+-----+-----+

このSegmentTree配列を構成する時間と空間の複雑さは、 O(n)です.nはItem配列の要素の数です。私たちの構築したSegmentTree配列を使って、 Range Minimum Query（RMQ）を実行することができます。 Range Maximum Queryを実行する配列を作成するには、次の行を置換する必要があります。

SegmentTree[position] := min(SegmentTree[2*position+1], SegmentTree[2*position+2])

with：

SegmentTree[position] := max(SegmentTree[2*position+1], SegmentTree[2*position+2])

範囲最小問合せの実行

RMQを実行する手順は、すでに序論に示されています。レンジ最小問合せを検査するための擬似コードは次のようになります。

Procedure RangeMinimumQuery(SegmentTree, qLow, qHigh, low, high, position):
if qLow <= low and qHigh >= high        //Total Overlap
    Return SegmentTree[position]
else if qLow > high || qHigh < low      //No Overlap
    Return infinity
else                                    //Partial Overlap
    mid := (low+high)/2
    Return min(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
               RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))
end if

ここでは、 qLow = The lower range of our query 、 qHigh = The upper range of our query qLow = The lower range of our query qHigh = The upper range of our query 。 low = starting index of Item array 、 high = Finishing index of Item array 、 position = root = 0 。これまでに作成したサンプルを使用して手順を理解してみましょう。

私たちのSegmentTree配列：

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
|  -1 |  -1 |  0  |  -1 |  2  |  4  |  0  |
+-----+-----+-----+-----+-----+-----+-----+

範囲[1,3]の最小値を求めたい。
これは再帰的なプロシージャなので、 qLow 、 qHigh 、 low 、 high 、 position 、 mid 、およびcalling lineを追跡する再帰テーブルを使用して、 RangeMinimumQueryの操作を確認します。最初に、我々はSegmentTree、1、3、0、3、0（RangeMinimumQueryを呼び出します。ここでは、最初の2つの条件が満たされていない（部分的に重複）。我々が得るでしょうmid 。 calling lineいるかを示すRangeMinimumQuery 、この後に呼び出されますステートメント内のRangeMinimumQuery呼び出しは、プロシージャ内でそれぞれ1と2と指定されています。表は次のようになります。

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+

RangeMinimumQuery-1を呼び出すと、 low = 0 、 high = mid = 1 、 position = 2*position+1 = 1渡されます。あなたが気付くことができることの1つは、 2*position+1はノードの左の子です。つまり、 ルートの左の子をチェックしています。 [1,3]部分的にオーバーラップが[0,1]、最初の2つの条件が満たされていないので、我々が得るmid 。私たちのテーブル：

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   1  |     1    |  0  |       1      |
+------+-------+-----+------+----------+-----+--------------+

次の再帰呼び出しでは、 low = 0 、 high = mid = 0 、 position = 2*position+1 = 3を渡します。私たちは私たちの木の一番左の葉に達します。 [1,3]は[0,0]と重複しないので、呼び出し関数にinfinityを返します。再帰テーブル：

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   1  |     1    |  0  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   0  |     3    |     |              |
+------+-------+-----+------+----------+-----+--------------+

この再帰呼び出しは完了しているので、再帰テーブルの前の行に戻ります。我々が得る：

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   1  |     1    |  0  |       1      |
+------+-------+-----+------+----------+-----+--------------+

ここでは、 RangeMinimumQuery-2呼び出しを実行します。今回は、 low = mid+1 = 1 、 high = 1 、 position = 2*position+2 = 4を渡します。私たちのcalling line changes to **2**ます。我々が得る：

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   1  |     1    |  0  |       2      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  1  |   1  |     4    |     |              |
+------+-------+-----+------+----------+-----+--------------+

だから私たちは前のノードの右の子に行きます。今回は全体が重なっています。値SegmentTree[position] = SegmentTree[4] = 2を返します。

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+

呼び出し元の関数に戻り、2つの呼び出し関数の2つの戻り値のうち、最小値が何であるかを確認しています。明らかに最小値は2です。呼び出し関数に2を返します。私たちの再帰テーブルは次のようになります。

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+

私たちはセグメントツリーの左の部分を見ています。ここからRangeMinimumQuery-2を呼び出します。 low = mid+1 = 1+1 =2 、 high = 3 、 position = 2*position+2 = 2渡します。私たちのテーブル：

+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  0  |   3  |     0    |  1  |       1      |
+------+-------+-----+------+----------+-----+--------------+
|   1  |   3   |  2  |   3  |     2    |     |              |
+------+-------+-----+------+----------+-----+--------------+

総重複があります。したがって、値SegmentTree[position] = SegmentTree[2] = 0を返します。この2人の子供が呼ばれた場所からの再帰に戻り、 （4,0）の最小値、つまり0を返し、値を返します。

手続きを実行した後、 0を得る。これは、インデックス1からインデックス3までの最小値である。

このプロシージャの実行時の複雑さは、 O(logn)ここで、 nはItems配列内の要素の数です。 Range Maximum Queryを実行するには、次の行を置き換える必要があります。

Return min(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
               RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))

with：

Return max(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
               RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))

レイジー伝播

たとえば、セグメントツリーをすでに作成しているとします。配列の値を更新する必要があります。これにより、セグメントツリーのリーフノードだけでなく、一部のノードの最小値/最大値も変更されます。これを例を見てみましょう：

これは8要素の最小セグメントツリーです。あなたにすばやく思い出させるために、各ノードはそれらの横に記載されている範囲の最小値を表します。たとえば、配列の最初の項目の値を3つ増やしたいとしましょう。どうすればそれをすることができますか？私たちはRMQを行った方法に従います。プロセスは次のようになります。

最初は、ルートをトラバースします。 [0,0]は[0,7]と部分的に重なり合うので、両方向に進みます。
- 左のサブツリーでは、 [0,0]は[0,3]と部分的に重なっています。両方向に進みます。
  - 左のサブツリーでは、 [0,0]は[0,1]と部分的に重なっており、両方向に移動します。
    - 左サブツリーで、[0,0]全く[0,0]と重なって、その葉ノードから、我々は3で、それは値s増加させることによって、ノードを更新します。 -1 + 3 = 2の値を返します。
    - 右のサブツリーでは、 [1,1]は[0,0]と重ならないので、ノード（ 2 ）の値を返します。
      これら二つの返された値の最小値（2、2）2であるので、我々は、現在のノードの値を更新し、それを返します。
  - 右のサブツリー[2,3]は[0,0]と重複しません。ノードの値を返します。（ 1 ）。
    これら二つの返された値の最小値（2、1）1であるので、我々は、現在のノードの値を更新し、それを返します。
- 右のサブツリー[4,7]は[0,0]と重複しません。ノードの値を返します。（ 1 ）。
最後に、2つの戻り値（1,1）の最小値が1であるため、ルートノードの値が更新されます。

単一のノードを更新するには、 O(logn)時間の複雑さが必要であることがわかります。ここで、 nはリーフノードの数です。したがって、ノードをiからjに更新するように要求された場合、 O(nlogn)時間の複雑さが必要になります。これはnの大きな値に対して煩雑になる。 怠惰になりましょう。つまり、必要なときにのみ働きます。どうやって？インターバルを更新する必要がある場合、ノードを更新し、更新が必要な子ノードをマークし、必要に応じてノードを更新します。このために我々は、セグメントツリーと同じサイズの怠惰な配列を必要としています。最初、 レイジー配列のすべての要素は、保留中の更新がないことを表す0になります。 lazy [i]にゼロ以外の要素がある場合、この要素はクエリ操作を行う前にセグメントツリーのノードiを更新する必要があります。どうすればそれをするつもりですか？例を見てみましょう：

例のツリーでは、いくつかのクエリを実行したいとしましょう。これらは：

[0,3]を3だけ増分します。
[0,3]を1だけ増分します。
[0,0]を2だけ増分します。

[0,3]を3だけ増分する：

ルートノードから開始します。最初に、この値が最新であるかどうかを確認します。このために、 レイジー配列が0であることを確認します。これは、値が最新であることを意味します。 [0,3]は[0,7]と部分的に重なり合う。だから我々は両方の方向に行く。
- 左のサブツリーには、保留中の更新はありません。 [0,3]全く[0,3]重なります。そこで、ノードの値を3で更新します。したがって、値は-1 + 3 = 2になります。今回は、一生懸命に行くつもりはありません。下がるのではなく、現在のノードのレイジーツリーの対応する子を更新し、それらを3ずつ増やします。現在のノードの値も返します。
- 右のサブツリーには保留中の更新はありません。 [0,3]は重ならない[4,7] 。したがって、現在のノード（1）の値を返します。
  2つの返された値の最小値（2、1）1です。ルートノードを1に更新します。

私たちのセグメントツリーとレイジーツリーは次のようになります：

レイジーツリーのノードの非ゼロ値は、それらのノードおよびその下位に保留中の更新があることを表しています。必要に応じて更新します。範囲[0,3]の最小値は何かを求められたら、ルートノードの左のサブツリーに来るでしょう。保留中の更新がないので、正しい2が返されます。したがって、このプロセスはセグメントツリーアルゴリズムの正確さには影響しません。

[0,3]を1ずつ増やす：

ルートノードから開始します。保留中の更新はありません。 [0,3]は[0,7]と部分的に重なり合う。私たちは双方向に行きます。
- 左のサブツリーには、保留中の更新はありません。 [0,3]完全[0,3]重なります。現在のノードを更新する： 2 + 1 = 3 。これは内部ノードなので、レイジーツリーの子ノードを1つ増やして更新します。現在のノード（ 3 ）の値も返します。
- 右のサブツリーには保留中の更新はありません。 [0,3]は重ならない[4,7] 。現在のノード（ 1 ）の値を返します。
我々は2つの戻り値（3,1）の最小値をとることにより、ルートノードを更新します。

私たちのセグメントツリーとレイジーツリーは次のようになります：

ご覧のように、Lazy Treeに更新情報を蓄積していますが、それを押し下げるわけではありません。これはレイジー伝播の意味です。私たちがそれを使用しなかったならば、値を葉にプッシュしなければなりませんでした。これは、不必要な時間の複雑さを増やすことになりました。

[0,0]を2増やす：

ルートノードから開始します。ルートは最新で[0,0]は部分的に[0,7]と重なっているので、両方向に移動します。
- 左のサブツリーでは、現在のノードは最新であり、 [0,0]は部分的に[0,3]と重なっています。両方向に移動します。
  - 左のサブツリーでは、レイジーツリーの現在のノードはゼロ以外の値を持ちます。したがって、まだこのノードに伝播されていない更新があります。セグメントツリーでこのノードを最初に更新します。これは-1 + 4 = 3になります。そして、私たちはこの4をレイジーツリーの子孫に伝播させます。現在のノードをすでに更新しているので、レイジーツリーの現在のノードの値を0に変更します。それで[0,0]は部分的に[0,1]と重なり合うので、両方向に進みます。
    - 左側のノードでは、レイジーツリーの現在のノードにゼロ以外の値があるため、値を更新する必要があります。したがって、値を-1 + 4 = 3に更新します。今、以降[0,0]全く[0,0]、我々は= 5 3 + 2に、現在のノードの値を更新重なります。これはリーフノードなので、値をもう伝播する必要はありません。全ての値がこのノードまで伝搬されているので、レイジーツリーの対応するノードを0に更新する。現在のノード（ 5 ）の値を返します。
    - 右側のノードでは、値を更新する必要があります。したがって、値は4 + 2 = 6になります。 [0,0]は[1,1]と重ならないので、現在のノード（ 6 ）の値を返します。レイジーツリーの値も0に更新します。これはリーフノードなので、伝播は必要ありません。
      我々は2つの戻り値（5,6）の最小値を使用して、現在のノードを更新します。現在のノード（ 5 ）の値を返します。
  - 右側のサブツリーには保留中の更新があります。ノードの値を1 + 4 = 5に更新する。これはリーフノードではないので、レイジーツリーの子ノードに値を伝播し、現在のノードを0に更新します。 [0,0]は[2,3]と重複しないので、現在のノード（ 5 ）の値を返します。
    我々は、返された値（5,5）の最小値を使用して、現在のノードを更新して値を返す（5）。
- 右のサブツリーでは保留中の更新はなく、 [0,0]は重複しないため[4,7] 、現在のノード（ 1 ）の値を返します。
我々は2つの戻り値（5,1）の最小値を使用して、ルート・ノードを更新します。

私たちのセグメントツリーとレイジーツリーは次のようになります：

[0,0]の値は、必要に応じてすべての増分を得ていることがわかります。

今度は範囲[3,5]の最小値を求めるように求められたら、これまでのことを理解していれば、クエリの実行方法を簡単に理解でき、戻り値は1になります。私たちのセグメントツリーとレイジーツリーは次のようになります：

私たちは、保留中の更新のためにレイジーツリーをチェックするという制約を加えたRMQを見つけるのと同じプロセスをたどりました。

もう一つは、現在のノードの子ノードが何であるかを知っているので、各ノードから値を返すのではなく、単にこれらのノードの最小値を見つけることができます。

Lazy Propagationで更新するための擬似コードは次のようになります。

Procedure UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
                                endRange, delta, low, high, position):
if low > high                                                //out of bounds
    Return
end if
if LazyTree[position] is not equal to 0                      //update needed
    segmentTree[position] := segmentTree[position] + LazyTree[position]
    if low is not equal to high                              //non-leaf node    
        LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + delta
        LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + delta
    end if
    LazyTree[position] := 0
end if
if startRange > low or endRange < high                       //doesn't overlap
    Return
end if
if startRange <= low && endRange >= high                     //total overlap
    segmentTree[position] := segmentTree[position] + delta
    if low is not equal to high
        LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + delta
        LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + delta
    end if
    Return
end if
//if we reach this portion, this means there's a partial overlap
mid := (low + high) / 2
UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
                                endRange, delta, low, mid, 2 * position + 1)
UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
                                endRange, delta, mid + 1, high, 2 * position + 2)
segmentTree[position] := min(segmentTree[2 * position + 1], 
                                                    segmentTree[2 * position + 2])

レイジー伝播でのRMQの疑似コードは次のようになります。

Procedure RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh, low, high, position):
if low > high
    Return infinity
end if
if LazyTree[position] is not equal to 0                      //update needed
    segmentTree[position] := segmentTree[position] + LazyTree[position]
    if low is not equal to high
        segmentTree[position] := segmentTree[position] + LazyTree[position]
    if low is not equal to high                              //non-leaf node    
        LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + LazyTree[position]
        LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + LazyTree[position]
    end if
    LazyTree[position] := 0
end if
if qLow > high and qHigh < low                                //no overlap
    Return infinity
end if
if qLow <= low and qHigh >= high                              //total overlap
    Return segmentTree[position]
end if
//if we reach this portion, this means there's a partial overlap
mid := (low + high) / 2
Return min(RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh, 
                                        low, mid, 2 * position + 1),
           RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh,
                                        mid + 1, high, 2 * position + 1)

Modified text is an extract of the original Stack Overflow Documentation

ライセンスを受けた CC BY-SA 3.0

所属していない Stack Overflow

data-structures
セグメントツリー

サーチ…

セグメントツリーの概要

配列を用いたセグメントツリーの実装

範囲最小問合せの実行

レイジー伝播